다음을 기억해두자.

$ab=n\to \min(a,b)\le \sqrt n$

기본 소수 판정

이를 바탕으로 기본적인 소수 판정 알고리즘을 짜보자. 시복은 $O(\sqrt n)$이다.

bool isPrime(int n) {
    if (n <= 2) return n-1;
    for (int x = 3; x*x <= n; x += 2)
	if (n%x == 0) return false;
    return true;
}

에라토스테네스의 체

다음의 sieve 배열은 합성수일 때 1을 나타낸다.

REP(x,2,n) if (!sieve[x])
    for (int u = 2*x; u <= n; u += x) sieve[u] = 1;

$\sum_{x=2}^{n}\left \lfloor \frac{n}{x} \right \rfloor=\left \lfloor \frac{n}{2} \right \rfloor+\left \lfloor \frac{n}{3} \right \rfloor+\left \lfloor \frac{n}{4} \right \rfloor+\cdots \leq \left \lfloor \frac{n}{2} \right \rfloor+\left \lfloor \frac{n}{2} \right \rfloor+\left \lfloor \frac{n}{4} \right \rfloor+\cdots = O(n \log n)$
$\sum_p\left \lfloor \frac np \right \rfloor=\left \lfloor \frac{n}{2} \right \rfloor+\left \lfloor \frac{n}{3} \right \rfloor+\left \lfloor \frac{n}{5} \right \rfloor+\cdots = O(n \log \log n)\approx O(n)$
$_\text{by Mertens' second theorem}$

결론적 최적화 코드

ⅰ ❫ 𝑂( Q×√N ) < 𝑂( N )

쿼리가 적다면 할 만하다. 첫 번째 그 코드이다.

ⅰⅰ ❫ 𝑂( N ) < 𝑂( Q×√N )

전처리라서 쿼리가 많을 때 유리하다. 두 번째 그 코드이다.

ⅰⅰⅰ ❫ 𝑂( N+Q×√N/㏒√N ), 약 N < 10¹⁶

수가 큰데 쿼리가 적으면 쓸 만하다. 다음의 sieve를 전처리하면서 prime list를 만들어 놓았다고 가정하자.
primes.back()² ≥ x에 대해서 100%의 확률로 작동한다.

bool isPrime(int x) {
    if (x < n) return !sieve[n];
    for (int p : prime)
	if (!(x%p)) return false;
    return true;
}

ⅰⅰⅰⅰ ❫ 𝑂( Q×log³N ), N > 10¹⁶

밀러-라빈 소수 판정법 (Miller-Rabin Primality Test)를 이용한다.
일반적인 long long 정도의 소수들은 쉽게 걸러낼 수 있다.
한국 자료로는 이 링크가 제일 깔끔한 것 같다.
사실은 시간 복잡도가 $O(k\log^3n)$으로 조금 더 걸리긴 한다. (적당한 범위 내에서 $k$는 10보다 작아 무시할 만하다.)