(정수론/파이썬) 소수 목록을 만들어 인수를 찾는다

* 소수 목록을 텍스트 파일로부터 읽어들여 피클 파일로 저장한다.

* 피클 파일의 소수 목록을 읽어들여 원하는 수의 인수분해를 한다. (인수를 찾는다. 못 찾으면 아무것도 출력하지 않음)

 

# 미리 상당량의 소수를 찾아놓고 이 소수를 활용해 큰수를 인수분해한다.
# 아주 큰수의 경우 인수분해가 잘 안 되는 경우가 있다.
# 예) 36799544363760852850158472813746772001249695467027553135084459191495404143126861597208894503131059724016325719
# 모든 자연수는 소수의 곱으로 표현가능하다,라는 정리에 착안해, 큰수를 소수로만 나눠본다.
# 실시간으로 소수를 구해 활용하는 것은 시간이 많이 걸리는 일인지라, 
# 소수를 미리 구해서 피클 파일로 저장한 다음,
# 1. 피클 파일이 없으면 지정한 텍스트 파일에서 소수를 읽어 피클 파일로 저장한다.
# 2. 피클 파일이 있으면 피클 파일에서 소수를 읽어 큰수를 소인수분해한다(약수를 구한다).


import pickle
import os.path

# 모든 양의 정수는 소수의 곱으로 표현가능하다,라는 정리에 기반하여
# 큰수를 소수로만 나누어서 소인수를 구함
def getDivisors(num, primes):
    n = num     # num을 복사해서 사용, 값 변경 예정
    for p in primes:   # 소수 목록에서 하나씩 가져와서 n을 나눠봄
      if n % p == 0:   # 나눠진다면 n을 재설정하고 인수 p를 기록
        n = n // p
        print(p, n)


# 텍스트 파일을 읽어 정수로 변환한 다음 피클 파일로 저장한다
def make_pkl_from_txt(txt_filename, pkl_filename):
    f = open(txt_filename, 'r')
    primes = []  # 소수를 저장할 리스트
    while True:
        line = f.readline()
        if not line: break
        prime = line.strip()
        if prime != '':
            primes.append(int(prime))
        #print(line)
    f.close()
    # 소수 2를 제일 처음에 끼워넣기
    #primes.insert(0, 2)

    length = len(primes)       # 소수 개수 출력
    lst = primes[length-100:]  # 마지막 100개 출력

    ## pickle 파일로 바꾸기
    with open(pkl_filename, 'wb') as pf:
        pickle.dump(primes, pf)

    ## 불러와서 저장 전 데이터와 합치하는지 검증
    with open(pkl_filename, 'rb') as pf:
        data = pickle.load(pf)

    length2 = len(data)
    lst2 = data[length-100:]

    if length == length2 and lst == lst2:
        print(lst2)
        print("원 데이터와 피클 파일에서 불러온 데이터가 일치합니다.")
        print("데이터 갯수: ", length2)
    else:
        print("데이터 정합성에 문제가 생겼습니다.")
    print()

#txt_filename = "get_primes_py.txt"   # 소수가 저장되어 있는 파일
txt_filename = "get_primes_UINT.txt"

#pkl_filename = "test_py.pkl"   # 피클을 저장할 파일
pkl_filename = "primes_lines_UINT.pkl"

# 피클 파일이 없다면 텍스트 파일로부터 피클 파일을 생성한다.
if os.path.isfile(pkl_filename) == False:
    make_pkl_from_txt(txt_filename, pkl_filename)

# 피클 파일에서 데이터를 불러온다
with open(pkl_filename, 'rb') as pf:
    primes = pickle.load(pf)

# UINT_MAX             4294967295 : 42억
# ULONG_MAX  18446744073709551615 : 1844경6744조737억9551615
# x / ln(x) : x 이하 소수의 대략적 개수
# UINT_MAX 이내 소수 개수: 193,635,250     1억9천 개
# ULONG_MAX 이내 소수 개수: 415,828,534,307,635,072   41경 5828조 개

#big_number = 10000128400406539
#big_number = 36799544363760852850158472813746772001249695467027553135084459191495404143126861597208894503131059724016325719
big_number = 14982300945943290918090909454983788547895985895893455426
#big_number = 7491150472971645459045454727491894273947992947946727713
#big_number = 5232382377407424196789580920854198603984134573

getDivisors(big_number, primes)  # 인수분해할 숫자와 소수 목록을 함수로 넘긴다

출력

2 7491150472971645459045454727491894273947992947946727713
1431690181 5232382377407424196789580920854198603984134573

 

(1억 2천여만개의 소수 목록으로 작업했을 경우) 15초 걸림