[팁] O(1) 소수 판별 함수.

제가 prime ring problem (이하 PRP) 문제를 구현하면서,

가장 속도가 느린 부분은, 어떤 수가 '소수이냐 아니냐?'를 판별하는 것이었습니다.

일반적인 소수 판별 알고리즘은, 간단하게는 그냥 나눠 보는 것 부터 시작해서, 여러 알고리즘이 존재합니다.

그런데 PRP 에서는 n<=16 이라는 제한 조건이 있으므로, 16+15 = 31 까지의 소수만 판별하면 됩니다.

이런 경우 정말 단순 무식하게 구현하는게 최곱니다.

int is_prime(int n)
/* return value
-1 : invalid input range
0 : not prime number
1 : prime number
*/

{

static int prime_number[] =

{0, 0,1,1,0,1,0,1,0,0,0, 1,0,1,0,0,0,1,0,1,0, 0,0,1,0,0,0,0,0,1,0, 1};

if ((n<0) || (n>31) return -1;

return prime_number[n];

}

이렇게 구현하면 정말 O(1) 만에 소수 판별이 가능하지요.

여기서는 함수로 구현하고, 에러 체크까지 했지만, PRP 문제에서는 그런것 다 필요 없으니 빼버리고,

실제로도 코딩은 함수가 아니라 매크로 형태로 구현해 버리면 됩니다.

............

이런 극단적인 방법은 소수 범위가 정말 극한적으로 작을때나 가능합니다.

그런데, 정말 이렇게 구현해 버리면, 더 큰 n 에 대해서 처리가 안되니깐,

다른 데서 사용하기 위해서는 더 일반적이 경우를 고려해서 작성해야 합니다.

좀더 일반적으로 32비트 정수 범위(42억 이하)에서는 대략 다음과 같은 방법을 사용합니다.

1) 65536 크기를 가지는 배열 prime_number[] 을 만든다.

2) 1 ~ 65536 까지 고전적인 방법인 '에라토스테네스의 체'를 이용해서 소수를 모두 구하여, 소수이면 1 아니면 0 을 채운다.

3) 이 배열에서 소수가 몇개인지 세어, 소수 배열 prime_sequence[] 을 만든다. (주1 : 655개)

4) 위의 65K 배열에서 하나씩 찾아서 소수 배열 prime_sequence[] 에 집어 넣는다.

(주2 : 결과적으로 int prime_sequence[] = { 2, 3, 5, 7, 11, 13, 17, ...} 이란 배열을 만드는 것)

5) 만약 입력 값이 65536 보다 작으면, 배열 prime_number[] 을 이용해서 바로 답을 내준다.

6) 만약 입력 값이 65536 보다 크고 42억보다 작으면, prime_sequence[] 을 이용해서 655번 나눠보면 소수 판정이 가능하다.

(주3: 사실 이 범위의 대부분은 합성수이기 때문에, 2, 3, 5 ,7, 11, 13, 17 로 정도로 나눠보는 것만으로도 99%의 수는 합성수로 판별 가능함.)

참고로 prime_number[] 배열은 메모리가 허용하는 한도에서 조금 더 키우면, 약간의 속도 향상을 얻을 수 있습니다.

실제 사용할 때는 보통 100만개 정도 배열을 잡아서 100만 이하의 소수라면 바로 판별할 수 있도록 합니다.

...............

32비트 정수를 넘어가는 수에 대해서 애초에 그런 수를 다루는 것 부터가 귀찮아 집니다.

C 에서는 GMP 라이브러리를 사용하거나 ( https://gmplib.org/ )

문제는 이런거 쓰는 순간, 모든 코딩을 처음부터 다시해야 해서, 일반적인 알고리즘 문제에서는 신경쓰지 않습니다.

................

참고로 JAVA 의 IntInterger 글래스에는 '확률적으로 소수인지 판정하는 isProbablePrime() 이란 기기묘묘한 메소드가 존재합니다.

- 엔델 -