Primality test
Deterministic
순차 탐색
1
for i in range(3, sqrtN, 2):
- 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유
- 2를 제외한 소수는 홀수이므로 step 2
- https://github.com/umbum/leet-hub/tree/main/count-primes
에라토스테네스의 체(sieve_of_eratosthenes)는 \(n\)까지의 모든 소수를 찾는 데에는 적합하지만 이를 이용해 \(n\)이 소수인지를 판별하고자 하는 경우 메모리 접근 횟수가 크게 늘어나기 때문에 훨씬 느리다.
일반적인 방법은sqrtN과i를 둘 다 레지스터에 넣고add reg, 2해가며 나누고 비교하면 되기 때문에 메모리 접근이 거의 필요 없는 반면,
체를 사용하는 방법은i로 나눠지지 않으면 flag 배열에서i의 배수에 해당하는 부분에 모두False를 표시해야 하므로 각각에mov mem_addr, 0따위의 연산을 수행하게 되며 결과적으로 메모리에sqrtN번 접근하게 된다.
물론 배열에False표시가 되어 있는 원소에 대해서는 비교 연산만 하고 넘어가 나누는 연산은 수행하지 않지만, 이 보다는 메모리 접근이 훨씬 비싸다.
이런 식으로 연산자 종류에 따른 CPU 연산 수행 속도, 메모리 접근 오버헤드 등 고려해야 하는 요소가 많은 경우, 가장 영향을 크게 미치는 것이 무엇인지를 먼저 따져보는 것이 좋다. 메모리 접근 오버헤드에 비하면 CPU 연산 수행 속도 차이는 미미하기 때문이다.
* 에라토스테네스의 체의 경우 램 16G에서 python으로 돌렸을 때 N=10**7까지는 잘 돌아간다.
10**8부터는 굉장히 오래걸리는 듯. i7-8700에서 40초정도? 10**10부터는 메모리 에러.
* 모든 소수가 \(4n - 1\)과 \(4n + 1\) 둘 중 하나라는 말은, 2를 빼면 그냥 홀수라는 말과 같다.
Lucas–Lehmer primality test
en.wiki/Lucas-Lehmer_primality_test
단점 : 지수가 2가 아닌메르센 수 (\(M_p = 2^p-1\))에 대해서만 판정할 수 있음 장점 : 구현이 간단하다
구현 시 주의사항
1
2
3
4
for i in range(n-2):
s = (s\*s - 2) % M
if s % M == 0:
print("M is prime number")
\(p\)가 클 경우 s\*s - 2연산 결과가 매우 커지기 때문에 big integer를 사용해야 한다. python같은 경우 알아서 big integer 처리를 해주기 때문에 python을 사용하면 편하다. C/C++은https://gmplib.org/라이브러리를 사용해야 한다. big integer를 사용하더라도 수가 너무 크기 때문에 % M으로 나머지만 가져가야 메모리가 터지는 것을 막을 수 있다. \(\bmod\) 연산은 덧셈, 뺄셈, 곱셈에 대해서 분배 법칙이 성립하기 때문에 % M으로 나머지만 가지고 연산해도 된다. \((A * B) \bmod C = (A \bmod C * B \bmod C) \bmod C\)
- 나눗셈은 모듈로 역수를 이용해 곱셈으로 바꿔야 성립한다.