백준 #9020: 골드바흐의 추측

 

 

접근법

---

문제에서 주어진 가장 기본적인 규칙이 짝수라는 것이다. 

 

이 특정한 짝수를 두 수의 합의 형태로 나타낼 때, 가장 차이가 작은 것은 짝수를 2로 나눈 값을 나열하는 것이다.

 

예를 들어서, 10의 경우는 5 + 5가 될 것이고, 14의 경우는 7 + 7이 될 것이다.

 

따라서, 문제에서 원하는 답을 찾을 때는, 어찌 되었든 가장 중앙에서부터 시작해야 한다.

 

문제를 풀기 위해서 접근한 방법은 아래와 같다.

 

1.  최대값인 10,000까지의 소수로 이루어진 리스트를 우선 만들어 놓는다.
   
   
2. 입력값을 n 이라고 할 때, n의 가운데에서부터 시작해서 소수 리스트에 해당 값이 있는지 확인한다.
   
   
3. 없으면 다음 값, 또 그다음 값... 을 반복하여 중앙에서 가장 가까운 소수를 찾는다. (이하 x)
   
   
4. 이제 해당 소수와 가장 인접한 소수들 중에서 x와 더하여 n이 되는 소수를 찾는다.

 

풀이

---

 

# 최대값 10,000까지의 소수 리스트를 만드는 코드
N = 10000
arr = [i for i in range(0,N+1)]
arr[1] = 0
for i in range(2,N+1):
    if arr[i] == 0:
        continue
    for j in range(i*2,N+1,i):
        arr[j] = 0

# 중앙에서부터 시작해서 답을 찾는 과정
case = int(input())
for i in range(case):
    n = int(input())
    for i in range(n//2,1,-1):
        if bool(arr[i]) :
            if bool(arr[n-i]) :
                print(i, n-i)
                break

 

소수로 이루어진 리스트는 소수인 값에 대해서만 해당 숫자가 입력되어있다.

즉, [0, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0 ... ] 이와 같은 형태를 가지고 있다.

따라서, 아래 코드에서 리스트를 인덱싱할 때, 0이 아닌 값에 대해서만 소수, 즉 True가 되기 때문에

하나의 for문으로 문제를 해결할 수 있었다.

일단 중앙에서 1씩 빼가며 소수를 찾고, 소수인 i를 찾았을 때, 그 i와 반대 방향으로 인덱싱하는 n-i 가

서로 소수일 경우에만 print가 된다. 

이 때, break를 걸어주지 않으면 모든 경우의 수가 출력된다.

 

 

@ 문제 출처: 백준