[백준] 6588번: 골드바흐의 추측 (에라토스테네스의 체)

 

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

6588번: 골드바흐의 추측

이 문제는 먼저 에라토스테네스의 체를 이용하여 범위 내의 숫자 중 소수를 먼저 판별해야 한다.

 

그러면 에라토스테네스의 체를 파이썬 코드로 구현하는 방법부터 꼭 암기해두자!

 

https://wikidocs.net/21638

2. 소수 구하기 - 에라토스테네스의 체

위 내용을 참고하였다.

 

우선 소수인지 검사하는 함수 isPrime을 만든다.

 

n=100

def isPrime(a):
  if(a<2):
    return False
  for i in range(2,a):
    if(a%i==0):
      return False
  return True

for i in range(n+1):
  if(isPrime(i)):
    print(i)

 

에라토스테네스의 체

위의 코드는 해당 수보다 작은 모든 수로 나누어 보아서 소수인지 판단하는 방법으로, 소수의 정의에 충실한 방법이면서 무식하지만 가장 강력한 방법이다. 한 개의 소수를 구할 때는 그런대로 괜찮은 방법인데 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다. 소수를 구하기 위해 에라토스테네스가 제안한 방법은

다음과 같다.

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

 

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. (반복)

 

에라토스테네스의 체를 파이썬 코드로 표현하면 다음과 같다.

 

n=1000
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):
        a[j] = False
print(primes)

 

그렇다면 다시 문제로 돌아와서 풀이를 생각해보자.

 

파이썬 풀이

# 백준 6588번

from sys import stdin

array = [True for i in range(1000001)]

for i in range(2, 1001):
    if array[i]:
        for k in range(i + i, 1000001, i):
            array[k] = False

while True:
    n = int(stdin.readline())

    if n == 0: break

    for i in range(3, len(array)):
        if array[i] and array[n-i]:
            print(n, "=", i, "+", n-i)
            break