Post

Primality test

Deterministic

순차 탐색

1
2
for i in range(3, sqrtN, 2):

에라토스테네스의 체(sieve_of_eratosthenes)는 \(n\)까지의 모든 소수를 찾는 데에는 적합하지만 이를 이용해 \(n\)이 소수인지를 판별하고자 하는 경우 메모리 접근 횟수가 크게 늘어나기 때문에 훨씬 느리다.
일반적인 방법은 sqrtNi를 둘 다 레지스터에 넣고 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

ko.wiki/루카스-레머

en.wiki/Lucas-Lehmer_primality_test

단점 : 지수가 2가 아닌메르센 수 (\(M_p = 2^p-1\))에 대해서만 판정할 수 있음 장점 : 구현이 간단하다

구현 시 주의사항

github link

1
2
3
4
5
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\)

  • 나눗셈은 모듈로 역수를 이용해 곱셈으로 바꿔야 성립한다.

AKS primality test

wiki/AKS_primality_test

Probabilistic

Baillie–PSW primality test (BPSW)

wiki/Baillie-PSW_primality_test

This post is licensed under CC BY 4.0 by the author.