[Python] 백준 #6588 골드바흐의 추측

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

정답률이 낮은 문제!!!!

왜냐고!!!! 왜긴왜야.. 또 시간초과지 뭐.. ㅎ ㅎ ㅎ ㅎ

에라토스테네의 체를 이용하였는데도 시간 초과가 발생했다.

 

그 문제를 살펴보니

#시간 초과의 이유
#1.에라토스테네스의 체를 이용하여 홀수인 소수를 구하는 과정에서 n이 입력될때마다  에라토스 함수를 돌림
#2.함수 내에서 홀수인 소수를 저장하는 리스트를 따로 생성함
#3.처음에 a 인 부분을 구하면 그 다음 b의 구간은 n-b로 설정해야함

 

시간초과난 코드

#시간초과난 코드

import sys

def func():
    k=0
    List=[1]*(1000000+1)
    List[0]=0
    List[1]=0
    result=[]
    for i in range(1000000+1):
        if List[i]==1:           
            for j in range(2*i,1000000+1,i):
                List[j]=0
    
    for i in range(2,1000000+1):
        if i%2!=0 and List[i]==1:
            result.append(i)
            
    return result

List=func()
while True:
    n=int(sys.stdin.readline())
    if n==0:
        break
    else:
        check=0
        for i in range(n-1,-1,-1):
            for j in range(0,n-i+1):
                if List[i]+List[j]== n:
                    print(f"{n} = {List[j]} + {List[i]}")
                    check=1
                    break
            if check==1:
                break
        #반복문이 모두 끝났는데 check=0임        
        if check==0: #나타낼 수 없음
            print("Goldbach's conjecture is wrong.")
            break
            

통과~~~~

#시간 초과의 이유
#1.에라토스테네스의 체를 이용하여 홀수인 소수를 구하는 과정에서 n이 입력될때마다  에라토스 함수를 돌림
#2.함수 내에서 홀수인 소수를 저장하는 리스트를 따로 생성함
#3.처음에 a 인 부분을 구하면 그 다음 b의 구간은 n-b로 설정해야함
import sys

#홀수인 소수들만 남기기
def func():
    k=0
    List=[1]*(1000000+1)
    List[0]=0
    List[1]=0
    result=[]
    for i in range(1000000+1):
        if List[i]==1:           
            for j in range(2*i,1000000+1,i):
                List[j]=0
                
        if i%2==0: #짝수 모두 지우기
            List[i]=0
            
    return List

List=func()

while True:
    n=int(sys.stdin.readline())
    if n==0:
        break
    else:
        check=0
        for i in range(n-1,-1,-1):
            for j in range(0,n-i+1):
                if List[i] ==1 and List[j] ==1 and i+j== n:
                    print(f"{n} = {j} + {i}")
                    check=1
                    break
            if check==1:
                break
        #반복문이 모두 끝났는데 check=0임        
        if check==0: #나타낼 수 없음
            print("Goldbach's conjecture is wrong.")