다음을 기억해두자.

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

기본 소수 판정

이를 바탕으로 기본적인 소수 판정 알고리즘을 짜보자. 시복은 O(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;

x=2nnx=n2+n3+n4+n2+n2+n4+=O(nlogn)\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)
pnp=n2+n3+n5+=O(nloglogn)O(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)
by Mertens’ second theorem_\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(klog3n)O(k\log^3n)으로 조금 더 걸리긴 한다. (적당한 범위 내에서 kk는 10보다 작아 무시할 만하다.)

profile
이 블로그 관리 안 한지 오래됨 / 백준 dohoon

1개의 댓글

comment-user-thumbnail
2021년 2월 10일
답글 달기