[Python] 백준 9020번 - 골드바흐의 추측

문제

9020번: 골드바흐의 추측

[ 문제 조건 ]

• 골드바흐 수 : 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
• 골드바흐 파티션이 여러개 인 경우는 두 소수의 차가 가장 작은 것이 답

[ 해결순서 ]

1. 이 문제를 해결하기 전에 에라토스테네스의 체가 무엇인지 알아야한다.

2. 소수인 값을 하나씩 기준으로 (이 값을 N이라 치자) N의 배수를 범위 내에 모두 지운다. 이걸 반복하고 반복문을 빠져나왔을 때 지워지지 않은 값이 소수인 것이다.

   • 에라토스테네스의 체 코드

     n = 100
     a = [False,False] + [True]*(n-1)
     primes = []
     
     for i in range(2, n+1): #n까지임 
         if a[i]: #값이 들어있으면 
             primes.append(i)
             # 2*i 인 이유는 그 값 이후의 두배 값부터 시작해야되므로 
             for j in range(2*i, n+1, i): #2*i~n+1까지 i만큼
                 a[j] = False
     print(primes)​

3. 먼저 에라토스테네스의 체 알고리즘으로 소수를 구했다.

4. 이 때 prime 배열에는 소수인 값은 True가 되어있다.

5. 이제 입력받은 각 값을 비교하는데 절반을 나누어서 반복 비교한다 ( 절반으로 나눠야 두개를 합쳤을 때의 값이 입력 값이 나오기 때문에 )

6. 값을 하나는 늘리고, 하나는 줄여서 두개의 값 모두 소수일 때 값을 출력하고 반복문을 빠져나온다.

✏️한줄평

: 에라토스테네스의 체(이름 한번 치기 넘 길다)에 대한 개념과 코드를 상기시킬 수 있는 문제였고, 그에 조금 더 응용된 문제였다.

---

코드