[백준/수학] 6588번: 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

문제

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

 

백만 이하의 짝수를 받으면, 해당 짝수를 두 홀수 소수의 합으로 표현하는 문제입니다.

아직 해결되지 않았다 했으므로, 나타낼 수 없는 경우를 작성하지 않았습니다.

 

풀이

에라토스테네스의 체를 통해, 백만 이하의 소수를 구합니다.

그리고, 2를 제외한 소수는 모두 홀수이므로 3부터 시작해서 더해서 원하는 짝수가 나오는 홀수 두 개를 찾습니다.

 

LIMIT = 1000001
prime_list = [True] * (LIMIT)

for i in range(2,1001):
    if prime_list[i]:
        for j in range(2*i,LIMIT, i):
            prime_list[j] = False


while True:
    x = int(input())
    if(x==0): break

    for i in range(3,LIMIT):
        if prime_list[i] and prime_list[x-i]:
            print(x, '=', i, '+' , x-i)
            break

---

 

에라토스테네스의 체

: 해당 수보다 작은 모든 수로 나누어 보아서 소수인지 확인하는 방법입니다.

 

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 채택하고, 나머지 2의 배수를 지웁니다.

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

4. 지워지지 않은 수 중 제일 작은 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)

https://wikidocs.net/21638

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