문제 32
소수 판정
자연수 $N$이 주어진다.
$N$이 소수라면 Yes를, 그렇지 않다면 No를 출력하라.
입력
첫 번째 줄에 자연수 $N$이 주어진다. $(1 \le N \le 10^{12})$
출력
$N$이 소수라면 Yes를, 그렇지 않다면 No를 출력한다.
예제 입력 1
29
예제 출력 1
Yes
예제 입력 2
100
예제 출력 2
No
공식 해설
$N$이 합성수라면 $N=ab$인 $2$ 이상의 정수 $a,b$가 존재한다. 두 수가 모두 $\sqrt N$보다 크면 곱도 $N$보다 커지므로 둘 중 하나는 반드시 $\sqrt N$ 이하이다.
따라서 $2$부터 $\lfloor\sqrt N\rfloor$까지 나누어떨어지는 수가 있는지만 확인한다. 하나라도 있으면 No, 없으면 Yes이다. 단, $1$은 소수가 아니므로 먼저 No로 처리한다.
최대 $10^6$까지만 검사하면 되므로 주어진 제한에서 충분하다. 시간복잡도는 $O(\sqrt N)$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
$N$과 나눌 수 $d$를 long long으로 저장한다. 반복 조건을 d <= N / d로 두면 제곱을 직접 계산할 필요가 없다. $N=1$은 반복 전에 소수가 아닌 것으로 처리한다.
C 구현
N을 long long으로 읽고 d <= N/d인 동안 약수를 검사한다. N이 1이면 소수가 아니다. sqrt의 반올림이나 d*d 중간 곱에 의존하지 않는다.
Python 구현
N < 2를 먼저 처리하고 2부터 math.isqrt(N)까지 약수를 검사한다. 짝수를 먼저 제외한 뒤 홀수만 검사해도 된다. isqrt는 부동소수 오차 없이 마지막 약수 후보를 포함한다.
Java 구현
long N을 사용하고 d <= N/d 조건으로 검사한다. 1을 따로 제외하며 Math.sqrt 결과를 int로 자르는 것보다 정수 조건이 명확하다.
Rust 구현
u64 N을 사용하고 N < 2를 제외한다. d <= N/d일 때 N%d를 확인하면 정확한 제곱근 경계에서 검사할 값을 빠뜨리지 않는다.
JavaScript 구현
$N\le10^{12}$이므로 입력과 $d^2$는 Number의 안전 정수 범위 안이다. $N<2$를 먼저 제외하고 d * d <= n인 약수 후보에 대해 n % d === 0을 확인한다.
짝수를 먼저 검사한 뒤 홀수만 시도하면 반복 수를 줄일 수 있다. $d^2=N$일 때도 검사하도록 <=를 유지한다. Math.sqrt의 반올림 결과에만 경계를 맡기거나 모든 계산에 BigInt를 사용할 필요가 없다.