ULONG_MAX인 18446744073709551615까지 소수를 구하려고 시도하다가 너무 큰 수라는 사실을 깨닫고,
UINT_MAX인 4,294,967,295 (42억...)까지만 시도하기로 했다. 2부터 UINT_MAX까지의 소수 개수는 UINT_MAX를 x로 놓으면, 대략 x/log(x) 와 비슷하다(자연로그). 고로 약 193,635,250로 2억개 가까이 된다. 현재 125,764,947까지 구해놓았는데 텍스트 파일로 저장하니 1.33GB가 나왔고 이를 피클 파일로 저장하니 670MB 정도가 나왔다.
소수를 이렇게 구하고 있는 까닭은 소인수분해를 하기 위해서다. 모든 정수는 소수들의 곱으로 표현할 수 있으므로 해당 정수를 소인수분해할 때 소수로만 나눠봐서 나눠지는지를 보면 된다. 해당 정수를 홀수로만 나누는 것에 비해 소수로만 나눈다면 10배 정도 빨리 처리할 수 있다. (UINT_MAX 이내에 2억개 가까이 소수가 있으니 대략 5% 정도가 소수라고 보면, 홀수로만 나눈다는 것은 모든 수의 50%를 사용하여 나눈다는 것이므로 소수만 사용하는 것이 10배는 속도가 빠르다. UINT_MAX를 넘어서면서 점점 소수 출현 빈도가 희박해지지만 그렇다고 갑작스레 낮아지는 것은 아니다. ULONG_MAX 이내에서 대략 2.2% 정도가 소수였던 걸로 기억...)
14982300945943290918090909454983788547895985895893455426 의 소인수 중 하나인 1431690181 (14억....)를 c 코드gmp 라이브러리로 찾아냈을 경우 30초가 걸렸고, 1억 3천만개 소수에 대한 정보(피클)를 가지고 동일한 수를 소인수분해해서 동일한 수를 찾아냈을 때 걸린 시간은 15초였다. 수가 커질수록 차이가 더 벌어질 수 있다.
125,764,947 번째 소수는 2,593,557,959 인데 그 소수 목록 중에 1,431,690,181이 포함되어 있어 가능한 일인데, 이 숫자는 소수 목록에서 71,489,278 인덱스에 위치하고 있다. 즉 대략 7억번을 홀수로 나누어봐서 이 수가 나왔다면(C언어 gmp로 30초 걸림), 소수 목록을 가지고 나누어보면 7천만번 만에 동일한 소인수를 구할 수 있었단 이야기다(파이썬으로 15초). 소수 목록 없이 조사한 것치고는 C의 GMP도 준수하다고 볼 수 있다.
어쨌든 이런 소수 목록을 만들자면 파이썬보다는 C언어가 훨씬 빠르다.
아래 소스 파일을 컴파일해서 ( -lgmp -lm 컴파일 옵션을 잊지 말자),
$ a.out > primes.txt
를 실행하면 개행문자로 구별된 소수 목록을 얻을 수 있다. 이것을 파이썬에서 readline으로 한줄씩 읽어서 정수로 변환해주고 그것을 모아서 피클 파일로 저장하면 된다. 이후에 그 피클 파일을 불러와서 그 소수 목록으로 해당 정수를 나누면 훨씬 빠르게 소인수 검색 작업을 할 수 있다.
#include <stdio.h>
#include <math.h>
#include <limits.h>
int isPrime(unsigned long num) {
unsigned long i, root_num;
root_num = (int)sqrt(num) + 1;
if (num <= 1) return 0; // 1 이하라면 소수 아님
if (num % 2 == 0) return 0; // 2의 배수라면 소수 아님
for (i = 3; i < root_num; i+=2)
if (num % i == 0)
return 0;
//printf("i = %lu", i);
return 1;
}
unsigned long getPrimes(unsigned long num) {
printf("2\n"); // 소수 2를 별도로 출력
// 속도를 위해 소수 2는 제외하고 3부터 홀수만 검사함. 2 외에는 짝수에 소수 없음.
for (unsigned long i = 3; i <= num; i+=2) {
if(isPrime(i)) //소수면 출력하거나 개수를 하나 올린다.
printf("%lu\n", i);
}
}
int main () {
//printf("UINT_MAX = %u\n", UINT_MAX); // 4294967295 : 42억
//printf("ULONG_MAX = %lu\n", ULONG_MAX); // 18446744073709551615 : 1844경6..조
getPrimes(UINT_MAX);
//getPrimes(ULONG_MAX);
return 1;
}출력:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
...