[백준] 1929 - 소수찾기(2) {시간초과이슈}

문제: www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

문제 자체는 간단하다. 그러나 이전 문제와 같은 방식으로 풀면 시간초과가 난다.

 

이전 문제: 2020/12/24 - [프로그래밍/문제 풀이] - [문제풀이/C] 백준 1978번 - 소수 찾기

[문제풀이/C] 백준 1978번 - 소수 찾기

이전 문제에서는 어떤 수가 소수인지 확인하기 위해 그 수를 2부터  (그 수 - 1)까지차례대로 나눴다.

 

만약 나머지가 0이 되는 수가 하나라도 있으면 그건 소수가 아니니까.

 

그러나 저 방법은 시간이 너무 오래 걸린다.

 

이 문제를 풀려면 에라토스테네스의 체 방식을 이용해야 한다.

 

설명은 주석으로 대체함