어떤 수가 소수인지 알아보려면 그 수의 제곱근값까지 나누어보면 알 수 있다.
조금 더 빠르게 개선하자면, 해당 수(num)가 짝수라면 합성수이므로 구체적으로 조사할 필요가 없고, 홀수일 경우만 취급하면 되는데, 홀수는 홀수로만 나누어지므로 3부터 시작해서 홀수로만 나누어보면 시간을 조금 줄일 수 있다.
더욱 빠르게 개선하자면, 모든 양의 정수는 소수의 곱으로 표현할 수 있으므로 (모든 수는 소인수분해가 가능하다는 뜻) 해당 정수를 소수로만 나누어보면 알 수 있다. num을 소수인지 판정하는 과정에서 소수를 구하자면 시간이 많이 걸린다. 파이썬보다는 C언어가 훨씬 빠르긴 한데, 그렇게 해도 무척 큰 수, 가령
3076382403662644884917201315295252005693733018156832251827714417
을 소인수분해하는 데는 시간이 제법 걸린다.
꽤 좋은 아이디어는 소수를 미리 구해 저장해놓고, 그 소수 목록을 불러와서 num을 나누어보는 방법이다.
C언어의 unsigned int 자료형 최대값인 UINT_MAX는 4,294,967,295(42억...)으로 이 이하의 소수 개수를 대충 추측하자면, UINT_MAX 를 x로 놓으면, x / ln(x) 값이 x 이하의 소수 개수와 대충 비슷하다.
>>> import numpy as np
>>> 4294967295/np.log(4294967295)
계산하면 193,635,250개가 나오고, 실제로 구해보니 203,280,221개가 나온다. 오차 범위 5% 내에 있다.
앞서 소개한 C코드로 소수를 구했다.
https://madrabbit7.tistory.com/123
(정수론/C) UINT_MAX까지 1억 9천만개 소수 구하는 코드 간소화
ULONG_MAX인 18446744073709551615까지 소수를 구하려고 시도하다가 너무 큰 수라는 사실을 깨닫고, UINT_MAX인 4,294,967,295 (42억...)까지만 시도하기로 했다. 2부터 UINT_MAX까지의 소수 개수는 UINT_MAX를 x..
madrabbit7.tistory.com
소수 2억개를 파이썬으로 구하는 데는 너무 오래 걸려서 (하룻밤 자고 나도 목표치에 아주 멀어서 며칠 걸릴 듯했다) C 언어로 구해보니 대략 8~12시간 정도 걸렸다. 처음에는 빠르게 구하는데 숫자가 억 단위로 커지면서 점점 느려지는 게 눈에 보였다.
갯수는 정확히 203,280,221 이고, 마지막 10개 소수를 출력해보면
$ tail primes_UINT_C.txt
4294967029
4294967087
4294967111
4294967143
4294967161
4294967189
4294967197
4294967231
4294967279
4294967291
$ head primes_UINT_C.txt
2
3
5
7
11
13
17
19
23
29
마지막 소수가 42억 9천 어쩌구이다.
C의 8바이트 자료형인 ULONG_MAX (unsigned long int의 최대값) 은 18446744073709551615인데, 1844경6744조737억9551615이다. 이 숫자 이내에서 소수를 모두 구하자면 엄청난 세월이 걸릴 것음을 뒤늦게 깨달았고, 그 소수들을 저장하는 데도 엄청난 용량이 필요할 것이다. 43억 이하의 소수들만 저장해도 텍스트 파일로 약 2.2GB이고 파이썬 피클 파일로 1.2GB가 나온다.
18446744073709551615 이내의 소수 숫자를 어림잡아보면 415,828,534,307,635,072 개로, 41경 5828조 어쩌구가 나온다. 무려 203,280,221의 2,045,592,691(20억...) 배에 달해서 그 소수들을 텍스트 파일로 저장하면 2.2GB * 20억의 용량이 나올 것이다.
내가 수학자이거나 소수를 찾는 데 혈안이 되어 있다면 500GB 정도 분량의 소수(2억개*25 = 50억개)를 구해서 SSD에 넣어두고, 소인수분해에 사용하겠다.
어쨌든 아래 사이트에 올려두었으니 필요하신 분은 사용하시기 바란다.
텍스트 파일: C언어를 사용해 UINT_MAX 까지의 소수를 구한 텍스트 파일
https://drive.google.com/file/d/1C5tWqF3HHNOo9hfBYG8ByJrtrcxPbeq5/view?usp=sharing
primes_UINT_C.zip
drive.google.com
피클 파일: 위의 텍스트 파일을 파이썬의 리스트 자료형으로 만들어 피클 파일로 저장한 것. 9월 21일 2번째로 저장했음을 표시.
https://drive.google.com/file/d/1IqA_JrUg7mKDdM66EqnAEkd3E2JS4I4Y/view?usp=sharing
primes_921_2_UINT.zip
drive.google.com
아래의 파이썬 코드를 사용해서 텍스트를 피클 파일로 변환할 수 있고, 피클 파일을 불러와서 어떤 정수가 소수로 나누어지는지 (소인수분해) 확인할 수 있다. 기억해야 할 점은 UINT_MAX 이내의 소수로 나누어봐서 나누어지지 않았다고 소수로 판정해서는 안 된다는 것이다. 그보다 더욱 큰 수로 나누어질 수도 있음을 기억해야 한다. 물론, 그럴 땐 페르마의 정리를 이용해 그 수가 합성수인지 '소수일 가능성 높음'인지 알 수 있다.
https://madrabbit7.tistory.com/124
(정수론/파이썬) 소수 목록을 만들어 인수를 찾는다
* 소수 목록을 텍스트 파일로부터 읽어들여 피클 파일로 저장한다. * 피클 파일의 소수 목록을 읽어들여 원하는 수의 인수분해를 한다. (인수를 찾는다. 못 찾으면 아무것도 출력하지 않음) # 미
madrabbit7.tistory.com
굳이 변환할 필요없이, 다운로드 받은 피클 파일을 그대로 사용할 수 있다. 어쨌든 상황에 맞게 txt_filename과 pkl_filename을 지정해줘야 한다. 지정된 피클 파일이 있으면 피클 파일을 별도로 만들지 않고 피클 파일에서 소수를 읽어와서 해당 정수를 소수로 나눈다. 처음에 txt 파일에서 피클 파일을 만드는 데 1분 정도의 시간이 걸릴 수 있다.
** 주의점: 2억개 소수를 한꺼번에 불러와서 하는 작업이다 보니 필자의 컴퓨터(i7 3770, 24GB 메모리)에서 위의 프로그램 실행시 약 8GB 메모리를 소모했다. 16GB 이상 컴퓨터에서 작업하시길 권한다.
** 소수를 찾는 과정이 재밌기는 한데, 시간이 많이 걸리는 점이 단점이다.