엄범


Deterministic

순차 탐색

```py
for i in range(3, sqrtN, 2):  # n은 홀수여야 하므로 step = 2
```

에라토스테네스의 체(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

단점 : 지수가 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


Probabilistic

Baillie–PSW primality test (BPSW)

wiki/Baillie-PSW_primality_test



'Algorithm > Theory' 카테고리의 다른 글

점근적 표기 / 평균 수행 시간 분석  (0) 2018.04.20
피보나치 수  (0) 2018.04.20
Quicksort  (0) 2018.04.08
Primality test  (0) 2017.11.19
재귀, recursion  (0) 2017.05.31
P, NP, NP-hard, NP-complete  (0) 2016.08.15