[Python/파이썬 6588 백준] 골드바흐의 추측

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

문제

짝수 n

n= a+b 식에서 a 와 b 둘다 소수인 경우를 출력하라 입니다.

출력 못하는 상황이 나오면 Goldbach's conjecture is wrong. 출력하고

0누르면 exit

입력

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

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

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

출력

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

 

풀이

시간초과가 엄청 나는 문제입니다.

한 8번만에 맞은거같아요

최대한 조건문을 줄이는게 핵심이구

에라토스테네스의 체를 이용하는 문제입니다.

 

처음에는 조합 쓰면서 풀어보려했는데 계속 시간초과나서

a,b 에서 b=n-a 인것을 이용해서

최대한 반복문을 줄여갔습니다.

 

pypy만 성공하구 python3 는 시간초과 여전히 납니다...

# 골드바흐의 추측
# 에라토스테네스의 체 
# 조건문 줄이기

import sys
import math
input=sys.stdin.readline

# 1000000까지 소수 판별
lst=[False,False]+[True]*1000000

for x in range(1000000+1):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:
            lst[x]=False
            break

while 1:
    n=int(input())
    if n==0:
        sys.exit()
    
    for i in range(3,(n//2)+1):
        if lst[i]==True:
            if lst[n-i]==True:
                # 6이 3+3 출력해서 넣어줬습니다.
                if i==n:
                    print("Goldbach's conjecture is wrong.")    
                    break
                else :
                    print("{0} = {1} + {2}".format(n,i,n-i))
                    break
            # n= a+b 중 어림잡아 a가 n의 절반 넘어가면 반복문 그만 돌게했습니다.
            elif i==n//2:
                print("Goldbach's conjecture is wrong.")    
                break