[백준 6588번-파이썬]골드바흐의 추측

백준 (BOJ) 6588번
https://www.acmicpc.net/problem/6588

사용언어 : PYTHON

1.문제

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 “Goldbach’s conjecture is wrong.”을 출력한다.

예제 입력

8
20
42
0

예제 출력

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

2.풀이

정수 n을 만들수 있는 a와 b의 조합을 돌아가며 홀수인 소수인지 판별하려고 했다.

12를 예로들어 생각해보았다.
12는 1+11, 2+10, 3+9, … 6+6 의 조합으로 구할 수 있다.
이때 1과 2는 홀수인 소수가 아니므로 제외할 수 있다.
이제 3부터 9까지의 숫자 조합 중 a와 b모두 소수인 조합을 찾으면 된다. 이때 a와 b는 위 그림처럼 대칭적으로 더하므로 3부터 n//2까지만 검사하면 된다.
이때 작은 수 부터 차례대로 검사하므로 제일 처음 발견된 a와b의 조합이 b-a가 가장 크게되고 골드바흐의 추측을 만족한다.

for i in range(3,n//2+1):
    if i와 n-i 모두 소수인지 검사!

이제 정수가 소수인지 아닌지 판단하기만 하면 되는데, 처음에는 정석적인 방법으로 isPrime 함수를 구현하였다. 이렇게 하면서도 시간제한이 1초인데 되려나..? 했지만 성공적으로 제출이 되었다.
하지만 에라토스테네스의 체를 사용하면 더 빠른 시간안에 성공할 수 있었다.

우선 정수 n의 범위가 (6 ≤ n ≤ 1000000) 이므로 1~1000000 까지 리스트를 만들었다. (인덱스는 0부터 시작하므로 1000001개를 만듬) 리스트의 초기값은 모두 True이다.

arr=[True]*1000001

그리고 2부터 시작하여 자신이 True이면 자신을 제외한 배수들은 모두 소수가 아니므로 False로 바꾼다. 이때 2부터 시작해서 1000001의 제곱근 까지만 반복하면 되는데 그 이유는 1000001의 제곱근 보다 커지면 이미 앞에서 했던 동작을 반복하는 의미없는 동작이 되기 때문이다. 자세한 내용은 여기.

for i in range(2,int(math.sqrt(1000001))+1):
    if arr[i]:
        for j in range(i+i,1000001,i):
            arr[j]=False

i+i 부터 i씩 더하는 것으로 range를 구성하여 간단하게 자신의 배수들을 False로 변경하였다.

3.코드

3-1. 처음 제출한 코드

import sys

input = sys.stdin.readline
def isPrime(n):
    for i in range(2,int(n**(1/2))+1):
        if n%i==0:
            return False
    return True

while True:
    n=int(input())
    if n==0:
        break

    for i in range(3,n//2+1):
        if i%2==0 or (n-i)%2==0:
            if i==(n//2):
                print("Goldbach's conjecture is wrong.")
                break
            continue

        if isPrime(i) and isPrime(n-i):
            print('%d = %d + %d'%(n,i,n-i))
            break

3-2. 에라토스테네스의 체를 사용한 코드

import sys
import math

input = sys.stdin.readline

arr=[True]*1000001

for i in range(2,int(math.sqrt(1000001))+1):
    if arr[i]:
        for j in range(i+i,1000001,i):
            arr[j]=False

while True:
    n=int(input())
    flag=0
    if n==0:
        break
    
    for i in range(3,n//2+1):
        if arr[i]==True and arr[n-i]==True:
            print('%d = %d + %d'%(n,i,n-i))
            flag=1
            break

    if flag==0:
        print("Goldbach's conjecture is wrong.")