[백준 알고리즘/Python] 6588 골드바흐의 추측

문제이해

예전에 풀어본 골드바흐 문제와 비슷합니다.

에라토스테네스의 체로 리스트를 소수화 합니다. 그리고 3부터 소수를 찾아서 가장 먼저 찾은 소수와 주어진 수를 빼서 그게 소수이면 그 조합이 답이 됩니다.

 

8 예를 들어  보겠습니다.

3부터 소수 찾으면 8에서 3을 빼봅니다. 5는 소수입니다. -> 짝수도 아닙니다. -> 출력합니다.

 

코드

import sys

a = [False, False] + [True] * (1000000)

#에라토스테네스의 체로 리스트a를 조정한다.
for i in range(2, 1000000):
    if(a[i]):
        for j in range(i*2, 1000000, i):
            a[j] = False
#여기서 리스트 a는 소수만 True

#소수를 구하는 함수
def prime_num(n):
    for i in range(3, n):
        #소수라면
        if(a[i]):
            if((a[n - i]) and ((n-i)%2 != 0)):
                print(n,"=",i,"+",n - i)
                return
    #두 홀수 소수의 합으로 n을 나타낼 수 없는 경우 
    print("Goldbach's conjecture is wrong.")


#0이 입력되기 전까지 while문 돈다.
test_case = int(sys.stdin.readline())
while(test_case != 0):
    
    prime_num(test_case)
       
    test_case = int(sys.stdin.readline())

 

 

#소수를 구하는 함수
def prime_num(n):
    for i in range(3, n):
        #소수라면
        if(a[i]):
            if((a[n - i]) and ((n-i)%2 != 0)):
                print(n,"=",i,"+",n - i)
                return
    #두 홀수 소수의 합으로 n을 나타낼 수 없는 경우 
    print("Goldbach's conjecture is wrong.")

주어진수 = n

3부터 1씩 증가하는 수 = i

소수들을 모아둔 리스트 a 에서 n-i를 뽑아봅니다. 그리고 2가 나올 수있으니 2를 조건에서 제외해줍니다.만약 있다면 함수를 종료하고 다음 입력을 기다립니다.

만약 3부터 n까지 도는데 일치하는 소수가 없다면

"Goldbach's conjecture is wrong."

를 출력하고 끝납니다.

 

여기서 

print(n,"=",i,"+",n - i)

print(n, "=", i, "+", n - i)하면 공백이 1칸 더생겨서 출력오류가 뜹니다.

 

print(n,"=",i,"+",n - i)으로 파이썬은 , 사이에 자동으로 공백을 넣어주는거 같습니다.