[소수 판별] 6588 백준 골드바흐의 추측

 문제 링크 www.acmicpc.net/problem/6588

 

 에라토스테네스의 체를 이용하라는 말도 있던데 사용 안 해도 통과 가능하다

 

 해당 수가 소수인지 아닌지는 1과 자기자신을 제외한 수로 나누어지는 지를 보면 된다

10 = 2*5 = 5*2 이기 때문에 소수가 아니다. 이와 같이 약수는 대칭되기 때문에 10의 경우 2까지만 검사해도 소수인지 아닌지 검사할 수 있다.

 

[풀이법]

① n의 가장 작은 약수는 sqrt(n) 이하이므로 2부터 sqrt(n) 이하까지 루프를 돌린다

② 두 수 중 하나라도 소수가 아니면 수를 증감하고 다시 소수인지 검사한다

 

[답코드]

import sys
input=sys.stdin.readline
 
def prime_number(a):
    for i in range(2, int(a**0.5)+1):
        if a%i==0:
            return 0
    return 1
 
while 1:
    a=int(input())
    if a==0:
        break
    left, right=3, a-3#+=2
 
    while not prime_number(left) or not prime_number(right):
        if right==3:
            print("Goldbach's conjecture is wrong.")
        right-=2
        left+=2
    print("%d = %d + %d" %(a, left, right))