(정수론/파이썬) 유클리드 아이디어를 이용해 새로운 소수 찾기

# '친절한 수론 길라잡이' 연습문제 12.1
# "소수가 무한히 많음을 증명하는 유클리드의 아이디어를 이용하여, 소수 목록 {5}로부터 
# 새로운 소수들을 찾아보아라. 찾아낸 수들이 너무 커서 소인수분해하기 힘들 때까지 반복해 보자.
# (1000 보다 작은 수는 소인수분해를 할 수 있으리라 기대한다.)

def isPrime(num):
  root_val = round(num ** 0.5) # 제곱근 값을 구한다
  for i in range(2, root_val+1): # 제곱근값+1 까지만 약수를 조사해도 충분하다
    if num % i == 0:  # 중간에 나눠지면 소수가 아니다
      return False
  return True   


# 소인수분해하여 그 목록을 돌려준다
# 가령 소인수분해 결과가 2^3*3^2*7 이라면,
# [2, 3, 7]을 돌려준다
def factorize_list(num):
  divisor_primes = [] # 분해된 인수를 차곡차곡 저장하는 리스트
  
  if isPrime(num): # 소수 판정
      return divisor_primes
  
  # 인수분해 루틴은 소수 판정 루틴과는 조금 다르게 접근할 필요가 있다.
  i = 2
  while True:
      # i가 소수인지 검사해서 소수라면 num을 i로 나눈다
      # i로 나눠서 나머지가 0이라면, 인수분해가 한번 된 것이다.
      if isPrime(i) and num % i == 0:
          divisor_primes.append(i) # 나누는 수를 저장 (가령, num이 12라면 i = 2)
          num = num // i   # 몫, 가령 24//2 = 12
          #print(f"{i}, {num}")
          # 12는 소수가 아니므로 반복문 계속. 소수가 나오면 그 소수를 저장하고 반복문 종료.
          if isPrime(num):
              divisor_primes.append(num)
              break  # return divisor_primes
          i = 2 # 인수분해를 한번 했으므로 숫자를 2로 다시 나눠보기로 설정
      else:
          i += 1 # 인수분해가 되지 않으면 젯수(나누는 수)를 1증가

  return sorted(set(divisor_primes)) # 중복 제거, 정렬하여 돌려주기


# 리스트에 든 숫자들을 모두 곱해서 결과를 돌려준다.
def multi(numbers):
  gop = 1
  for number in numbers:
    gop *= number
  return gop

  
primes = [2]  # 찾아낸 소수들을 담는 리스트

while True:
  new_num = multi(primes) + 1
  if isPrime(new_num): # 소수라면 소수 목록에 추가
    primes.append(new_num)
  else:                # 합성수라면 소인수분해한다.
    divisors = factorize_list(new_num)
    found = False
    for d in divisors: # 예: [2, 3, 7]
      if d not in primes: # 소수 목록에 없는 소수를 찾았다면, 목록에 추가
        primes.append(d)
        found = True  # 찾았음을 표시
        break
      # 만일 해당 소수가 이미 목록에 있다면 인수분해된 소수 중 다음 소수를 for 문으로 시도한다.
    if found == False: # 본인도 소수가 아니고 인수분해된 소수들이 이미 소수 목록에 들어 있다면 포기한다.
      print("소수를 찾을 수 없습니다.")
      exit(1)
  print(primes)
      
'''
# 소수 목록 {5}에서 시작했을 때의 결과...
[5, 2]
[5, 2, 11]
[5, 2, 11, 3]
[5, 2, 11, 3, 331]
[5, 2, 11, 3, 331, 19]
[5, 2, 11, 3, 331, 19, 199]
[5, 2, 11, 3, 331, 19, 199, 53]
[5, 2, 11, 3, 331, 19, 199, 53, 21888927391]
[5, 2, 11, 3, 331, 19, 199, 53, 21888927391, 29833]
...
# 소수 목록 {2}에서 시작했을 때의 결과...
[2, 3]
[2, 3, 7]
[2, 3, 7, 43]
[2, 3, 7, 43, 13]
[2, 3, 7, 43, 13, 53]
[2, 3, 7, 43, 13, 53, 5]
[2, 3, 7, 43, 13, 53, 5, 6221671]
[2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571]
...

이 이상은 숫자가 너무 커서 컴퓨터에서 처리하는 데 시간이 많이 걸림
'''