글 읽기 - ★☆★☆★ [필독] 소수 구하기 FAQ ★☆★☆★

djm03178 4년 전 50

몇 개의 수, 예를 들어 2, 3, 5, 7 정도로만 나누어보고 안 나누어 떨어지면 소수인 게 아닙니다. 이 수들로만 안 나누어 떨어지면 다른 수로는 절대로 안 나누어 떨어질까요? 121은 11 * 11이고 다른 소인수는 없습니다. 그럼 11까지 포함하면? 169는 13 * 13입니다. 문제에서 주어지는 수의 범위는 최대 100만이고, 정말로 모든 경우의 수를 손으로 짜넣어서 풀려면 997까지의 모든 소수 목록을 다 만들어봐야만 100만까지의 수를 다 판별할 수 있습니다. 예제에 주어진 범위가 작다고 해서 예제만 통과할 수 있는 범위 내에서 소수 판별을 하면 안 됩니다. 문제의 조건을 봐야 합니다.
각 수에 대해 소수 판별을 하기 위해 2부터 그 수 전까지를 모조리 나누어 보면 당연히 시간 초과입니다. 수의 범위가 100만까지인데, 이 중에 실제로 소수인 것은 78498개나 있고, 적어도 이들은 자신이 소수임을 판별하기 위해 자신의 크기만큼 루프를 돌아야 한다는 뜻이 됩니다. 그러면 대충 계산해 봐도 수십 억 번의 루프를 돌아야 하겠죠? 2초 내에 돌 수 있는 횟수가 아닙니다.
소수를 빠르게 판정하는 방법에는 여러 가지가 있지만, 그 중 가장 간단하면서도 시간 복잡도를 크게 개선시킬 수 있는 것은 그 수의 제곱근까지만 나누어보는 것입니다. 즉, i * i <= n일 때까지만 루프를 돌면서 하나라도 나누어 떨어지는 것이 있으면 소수가 아니고, 없으면 소수입니다. 왜 그럴까요? 만일 어떤 자연수 x에 sqrt(x)보다 큰 소인수가 존재한다면, x를 그 소인수로 나눈 값은 sqrt(x)보다 작아야 하기 때문에, 2부터 순차적으로 i를 증가시키는 동안 이미 그 수로 나누어보았을 것이기 때문입니다.
개별적인 수에 대해 하나씩 판별해도 되지만, 이와 같이 넓은 범위에 대한 소수 판별을 해야 할 때는 에라토스테네스의 체를 사용하는 것이 더 효율적입니다. 간단한 방법으로 N까지의 소수 목록을 O(N*log(log(N))) 시간에 구해낼 수 있습니다. 자세한 것은 구글링을 해보세요. 구글신을 믿으세요.
에라토스테네스의 체를 구현할 때 흔히 안쪽 루프를 int j = i * i로 시작하는데, 이렇게 하면 i가 46341이 되는 순간부터 i * i가 int의 범위를 초과하기 때문에 오버플로우가 발생합니다. long long을 사용하거나, i * i 대신 i * 2부터 시작하는 등의 방법을 사용하세요.
endl은 버퍼를 flush하기 때문에 너무 느립니다. '\n'을 대신 사용하세요.
1은 소수가 아닙니다. 잘 판정하는지 지금 바로 테스트 해보세요.
크기가 n인 배열을 할당받으면 인덱스는 n-1까지만 있습니다. 그러니까 int arr[n]; 혹은 int *arr = new int[n]; 이라고 해놓고 arr[n]에 접근하면 안 됩니다.
M 이상 N 이하입니다. 미만이 아닙니다.

kangsy763 4년 전 0

감사합니다

sait2000 4년 전 0

8번에 오타 있습니다. 당 -> 할당

djm03178 4년 전 0

수정했습니다.

plan222 4년 전 0

3번 참고해서 시간초과 문제 해결했습니다. 감사합니다!

ksjlinker 4년 전 0

구글링해서 코드들을 참고해봤는데, 도저히 성공이 안 되더라구요. 구글링 하는 것도 힘드네요.

satoly4 4년 전 1

매우 도움되는 팁들에 자세한 설명까지 감사합니다!

cordialdiscord 3년 전 0

초보자가 이해하기 쉬운 좋은 글 감사합니다

gazebo1 3년 전 0

와 endl 하고 \n이 차이가 많이 나네요... 좋은 정보 감사합니다.

bc5218 3년 전 0

와 꿀팁!

mnopw 3년 전 0

정말 ㄹㅇ 감사합니다 덕분에 문제를 해결할 수 있었습니다...

댓글을 작성하려면 로그인해야 합니다.