[백준] 골드바흐의 추측

출처:: www.acmicpc.net/problem/6588

분류:: 수학

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

 1. 에라토스테네스의 체 

#골드바흐의 추측
#https://www.acmicpc.net/problem/6588
import sys
import math
maxv=1000000
sosu=[True]*(maxv+1)
sosu[1]=False
for i in range(2,int(math.sqrt(maxv))+1): #소수구하기
    if sosu[i]:
        j=2
        while i*j<=maxv:
            sosu[i*j]=False
            j+=1


while True:
    n=int(sys.stdin.readline())
    a,b=0,0
    if n==0:
        break
    for i in range(3, n + 1, 2):
        if sosu[i] == True and i % 2 == 1 and sosu[n - i] == True and (n - i) % 2 == 1:
            a, b = i, n - i
            break
    if a!=0 and b!=0:
        print("%d = %d + %d" %(n,a,b))
    else:
        print("Goldbach's conjecture is wrong.")

 

3. 오답원인

  1. 시간초과 

  - 어떻게 해결할까... 1) 입력받을 때마다 소수 구할 필요 없음 

#골드바흐의 추측
#https://www.acmicpc.net/problem/6588
import sys
import math
sys.stdin = open("input.txt","r")
def gold(n):
    sosu=[True]*(n+1)
    sosu[1]=False
    for i in range(2,int(math.sqrt(n))+1): #소수구하기
        if sosu[i]:
           j=2
           while i*j<=n:
               sosu[i*j]=False
               j+=1

    for i in range(3,n+1,2):
        if sosu[i]==True and i%2==1 and sosu[n-i]==True and (n-i)%2==1:
            a,b=i,n-i
            return a,b
    return None,None

while True:
    n=int(sys.stdin.readline())
    if n==0:
        break
    a,b=gold(n)
    if a and b:
        print("%d = %d + %d" %(n,a,b))
    else:
        print("Goldbach's conjecture is wrong.")

 

4. 알게된 점