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

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

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

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

6588번: 골드바흐의 추측

 

풀이

골드바흐의 추측 : 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

 

1000000 이하의 짝수에서 골드바흐의 추측을 검증하는 문제이다.

 

우선 에라토스테네스의 체를 이용하여 1000000 의 홀수 소수를 구하고, 구해진 홀수 소수를 탐색하여 조건을 검증 하였다.

 

import sys

primes = [0, 0] + [1] * 1000000

for i in range(2, 1000001):
    if primes[i]:
        if i % 2 == 0:
            primes[i] = 0
            continue
        for j in range(i+i, 1000001, i):
            if primes[j]:
                primes[j] = 0

while True:
    N = int(sys.stdin.readline())
    if not N:
        break
    B = N-1
    A = 1
    while True:
        B -= 1
        A += 1

        if primes[B] and primes[A]:
            print(f"{N} = {A} + {B}")
            break