(정수론/파이썬) 골드바흐 추측 - 짝수의 모든 소수 조합 찾기

# '친절한 수론 길라잡이' 연습문제 13.2 골드바흐 추측 관련
# "a) 70과 100 사이의 모든 짝수가 두 소수의 합임을 확인하여라.
# b) 70을 70 = p + q와 같이 p <= q인 두 소수의 합으로 표현하는 서로 다른 방법은 몇 가지가 
# 있는가? 90, 98에 대해서는...?"

# 짝수, 가령 98을 입력하면 합이 98이 되는 두 소수의 목록, 즉 (19, 79), (31, 67), (37, 61)을
# 구하고 그 갯수 3을 출력하는 프로그램을 짠다.
# '골드바흐 추측 확인용 코드'를 조금 수정한다.

# 해당 숫자가 소수인지 판정하는 함수
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   # 끝까지 나눠지지 않을 경우, 소수로 판정하고 리턴한다.

# 숫자 num을 인자로 받는다.
# 2부터 시작해서 num/2까지 소수에 해당하는 숫자(i)로만 num - i 를 시도한다.
# num - i가 소수라면 num이 i와 num-1라는 두 소수로 표현되었으므로 이 둘을 저장하고,
# 같은 작업을 반복해서 다른 소수 커플을 찾아낸다.
def goldbach_findall(num):
  until = int(num/2) + 1 # 빼기 시도는 num / 2 까지 한다.

  answers = []

  for i in range(2, until): # 2 ~ num/2
    if i != 2 and i % 2 == 0: # 2가 아닌 2의 배수는 소수가 아니므로 건너뛴다
      continue
    if i != 3 and i % 3 == 0: # 3이 아닌, 3의 배수는 소수가 아니므로 건너뛴다
      continue
    if isPrime(i) == False: # 2의 배수도, 3의 배수도 아닌 합성수이면 건너뛴다. 소수만 취급하므로
      continue
    if isPrime(num - i):
      answers.append((i, num - i))
  return answers

num = 70
ans = goldbach_findall(num)
print(f"{num} : {len(ans)} 개  {ans}")

num = 90
ans = goldbach_findall(num)
print(f"{num} : {len(ans)} 개  {ans}")

num = 98
ans = goldbach_findall(num)
print(f"{num} : {len(ans)} 개  {ans}")

num = 888
ans = goldbach_findall(num)
print(f"{num} : {len(ans)} 개  {ans}")

결과:

70 : 5 개  [(3, 67), (11, 59), (17, 53), (23, 47), (29, 41)]
90 : 9 개  [(7, 83), (11, 79), (17, 73), (19, 71), (23, 67), (29, 61), (31, 59), (37, 53), (43, 47)]
98 : 3 개  [(19, 79), (31, 67), (37, 61)]
888 : 37 개  [(5, 883), (7, 881), (11, 877), (29, 859), (31, 857), (59, 829), (61, 827), (67, 821), (79, 809), (101, 787), (127, 761), (131, 757), (137, 751), (149, 739), (179, 709), (197, 691), (211, 677), (227, 661), (229, 659), (241, 647), (257, 631), (269, 619), (271, 617), (281, 607), (311, 577), (317, 571), (331, 557), (347, 541), (367, 521), (379, 509), (389, 499), (397, 491), (401, 487), (409, 479), (421, 467), (431, 457), (439, 449)]