(정수론/파이썬) 골드바흐 추측을 컴퓨터로 확인하기

# 골드바흐의 추정 : Goldbach's Conjecture
# 4 이상의 모든 짝수는 소수 두 개의 합으로 표현된다.

# ' 친절한 수론 길라잡이' 95쪽
# 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 12 = 5 + 7,
# 14 = 3 + 11, 16 = 3 + 13, 18 = 5 + 13, 20 = 7 + 13 ...

# 해당 숫자가 소수인지 판정하는 함수
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(=i)부터 시작해서 num/2 까지 소수에 해당되는 걸로만 해서 num - i를 시도한다.
# num - i가 소수라면 num이 i와 num-i 라는 두 개의 소수로 표현되었으므로 이 둘을 반환한다
def goldbach(num):
  # 이 변수 계산을 for문의 range 안에서 여러 수천, 수만 번 하지 않고 여기서 한번만 하는 것이 훨씬 효율적이다.
  until = int(num/2) + 1
    
  for i in range(2, until):
    # 2를 제외하고 짝수면 소수가 아니기 때문에 다음으로 넘어간다. 
    # 함수 호출해서 검사하면 오버헤드 발생하기 때문에 그냥 여기서...
    if i != 2 and i % 2 == 0:
      continue 
    if i != 3 and i % 3 == 0:
      continue
    if isPrime(i) == False: # 2의 배수도, 3의 배수도 아닌 합성수이면 다음으로 넘어간다
      continue
    if isPrime(num - i): # 이제 i 는 소수이므로 num - i 의 결과가 소수이면 두 값을 리턴한다
      return i, num - i
    
    
print(goldbach(20))
print(goldbach(200))
print(goldbach(350))
print(goldbach(470))
print(goldbach(12722))
print(goldbach(66))
print(goldbach(88882))
print(goldbach(43322))
print(goldbach(9892438))
print(goldbach(423898794))

# 4부터 2씩 올려 짝수만 검사한다
for j in range(4, 4309234092, 2):
  print(f"{j}: {goldbach(j)}" )

결과:

.....

22374: (5, 22369)
22376: (7, 22369)
22378: (11, 22367)
22380: (11, 22369)
22382: (13, 22369)
22384: (3, 22381)
22386: (5, 22381)
22388: (7, 22381)
22390: (23, 22367)
22392: (11, 22381)
22394: (3, 22391)
22396: (5, 22391)

....