Primality test

 

Deterministic

순차 탐색

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

ko.wiki/루카스-레머

en.wiki/Lucas-Lehmer_primality_test

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

장점 : 구현이 간단하다

 

구현 시 주의사항

github link

```py

for i in range(n-2):

    s = (s*s - 2) % M

if s % M == 0:

    print("M is prime number")

```

\\(p\\)가 클 경우 ``kt s*s - 2``연산 결과가 매우 커지기 때문에 big integer를 사용해야 한다. 

python같은 경우 알아서 big integer 처리를 해주기 때문에 python을 사용하면 편하다.

C/C++은 https://gmplib.org/ 라이브러리를 사용해야 한다.

big integer를 사용하더라도 수가 너무 크기 때문에 ``kt % M``으로 나머지만 가져가야 메모리가 터지는 것을 막을 수 있다.

\\(\bmod\\) 연산은 덧셈, 뺄셈, 곱셈에 대해서 분배 법칙이 성립하기 때문에 ``kt % 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