[백준] 6588번 : 골드바흐의 추측 (Python)

문제 : https://www.acmicpc.net/problem/6588

 

 

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

이 골든바흐의 추측을 백만 이하의 모든 짝수에 대해서 검증하는 문제다.

 

import sys

input = sys.stdin.readline

# 에라토스테네스의 체로 소수 구하기
def prime(N):
    
    a = [False,False] + [True]*(N-1)
    primes=[]

    for i in range(2,N+1):
        
      if a[i]: # 소수이면
        primes.append(i)
        
        for j in range(2*i, N+1, i): # i의 합성수를 지움
            a[j] = False
    
    return primes, a

get_prime_numbers = 1000000
primes, all_primes = prime(get_prime_numbers) # 소수 구하기

while(True):
    N = int(input()) # N
    
    if(N == 0): # 0이면 반복문 종료
        break;
        
    # 골든바흐의 추측 검증
    for i in primes:  
        
        if(i > N): # N 이하의 소수들만
            break;
        
        # 골든바흐의 추측이 맞으면
        if(all_primes[N-i] and all_primes[i]):
            print("%d = %d + %d" %(N, i, N-i))
            break;
    
    # 골든바흐의 추측이 틀리면
    else:
        print("Goldbach's conjecture is wrong.")

 

 

 

[문제풀이]

---

 

골든바흐의 추측을 검증하려면 숫자 N 이하의 소수를 하나씩 N에 빼볼 때 그 숫자가 소수이면 검증 완료다.

 

예)

N이 8일 때
소수 = [2, 3, 5, 7] <= 홀수 소수랬으니 2는 x

8 - 3 = 5 (검증완료)

 

 

이 방식으로 N을 검증하면 된다!