문제 33
소수 판정 2
자연수 $N$과 $Q$개의 쿼리가 주어진다.
각 쿼리마다 자연수 $x$가 소수라면 Yes를, 그렇지 않다면 No를 출력하라.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 10^7; 1 \le Q \le 200\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 자연수 $x$가 하나씩 주어진다. $(1 \le x \le N)$
출력
각 쿼리마다 $x$가 소수라면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
100 8 1 2 3 4 17 18 49 97
예제 출력 1
No Yes Yes No Yes No No Yes
공식 해설
질의마다 약수를 검사하는 대신, 가능한 모든 수의 소수 여부를 에라토스테네스의 체로 한 번에 구한다.
$0$과 $1$을 제외한 수를 소수 후보로 두고 $p=2$부터 $p^2\le N$까지 순회한다. 아직 지워지지 않은 $p$는 소수이므로 $p^2,p^2+p,\cdots$를 합성수로 표시한다. $p^2$보다 작은 $p$의 배수는 더 작은 소인수의 배수로 이미 처리되었다.
모든 합성수에는 제곱근 이하의 소인수가 있으므로 위 과정에서 반드시 지워진다. 소수는 다른 소수의 배수가 아니어서 지워지지 않는다. 따라서 남은 표시가 정확히 소수 여부이다.
각 질의는 $x$의 표시 한 칸을 확인하여 답한다. 시간복잡도는 $O(N\log\log(N+2)+Q)$, 공간복잡도는 $O(N)$이다.
구현 · 언어별 풀이
C++ 구현
합성수 여부를 vector<char>로 저장하고 $0$과 $1$을 별도로 제외한다. 배수를 지우는 시작점은 $p^2$이며 1LL * p * p처럼 곱하기 전부터 넓은 정수로 계산하면 안전하다. 체를 한 번 만든 뒤 각 질의에서는 배열 한 칸만 읽는다.
C 구현
소수 여부는 N+1칸의 unsigned char 배열로 저장한다. 0과 1을 제외하고 각 소수 p의 p*p부터 배수를 지운다. 배수 시작은 long long으로 곱한 뒤 범위 안의 인덱스로 바꾼다.
Python 구현
bytearray를 사용하여 천만 칸의 boolean 객체 목록을 피한다. p*p부터 간격 p로 0을 대입한다. 슬라이스 대입을 쓴다면 대상 원소 수와 같은 길이의 바이트열을 만들어야 한다.
Java 구현
boolean[]으로 합성수를 표시한다. 배수의 시작인 p*p를 계산할 때는 1L*p*p로 먼저 승격하여 조건 검사 중 int 오버플로를 피한다. 질의마다 소수 판정을 새로 하지 않는다.
Rust 구현
Vec<bool> 또는 Vec<u8>에 소수 표시를 둔다. p <= N/p 조건으로 체의 바깥 반복을 제어하고 p*p부터 배수를 지운다. 모든 질의는 완성된 배열에서 바로 조회한다.
JavaScript 구현
합성수 여부를 길이 n + 1의 Uint8Array에 표시하면 천만 개의 일반 객체 대신 약 천만 바이트의 상태로 체를 만들 수 있다. 기본값 $0$을 후보, 지운 값 $1$을 합성수로 쓰고 $0,1$도 먼저 표시한다.
아직 지워지지 않은 $p$에 대해 $p^2$부터 간격 $p$로 표시한다. 질의는 해당 칸 한 번만 확인한다. 번호와 제곱은 $10^7$ 이하이므로 Number로 충분하고, 질의마다 약수 검사를 다시 하지 않는다.