어떤수 x가 Prime인지 확인하는 방법:

1. Trial Division: sqrt(x) 까지의 모든 prime으로 나눠본다.

2. Sieve of Erathosthenes: x뿐만 아니라 x+1, x+2, … x+n과 같이 연속된 정수의 경우에 좋은 방법. 2부터 시작해서 2의 배수를 지움, 남은 수에서 가장 작은 odd number 남기고 그 배수를 지우는 것의 반복.

3. Wheel Factorization: 몇개의 prime number를 취한다. 예를들면 2와 3. 그 뒤, 2로 x가 나눠지는지 본다. 3으로 x가 나눠지는지 본다. 이제 더 큰수로 나누기 위해.. 6(=2*3)보다 작은 2와 3에 서로 소인 수를 찾아보면 1과 5. 이제부터 2, 3보다 큰수로 x를 나눠봐야 할텐데, 나눠보는 수로 6n+1, 6n+5를 사용함. 즉, 5, 7, 11, 13, 17, 19, … 로 x를 계속 나눠봄. 물론 이 경우에도 sqrt(x)보다 작은 수로만 나눠보면 됨. 이 방법의 경우 대부분의 경우에 prime number를 찾아낸다.

4. Fermat’s Little Theorem: x가 a를 나누지 않는 소수라면

$a^{(p-1)} = 1~(mod~p)$

를 만족해야함. 그렇지 않다면 x는 소수가 아님.