골드바흐의 추측

안녕하세요 :) Zedd입니다. 오늘은 골드바흐의 추측에 대해서 알아볼거에요 XD

시작할게요!

골드바흐의 추측

---

1742년, 독일의 수학자 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냅니다.

【4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 】

4 = 2 + 2

6 = 3 + 3

8 = 3 + 5

.

.

.

이를 이용하여 백준 1153번 네 개의 소수를 풀어볼게요.

먼저 문제를 잘 봐야할 것이 임의의 자연수가 주어지면 이를 "네 개의 소수"로 분해해야합니다.

골드바흐의 추측을 보면, 【4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 】였죠.

네 소수의 합이 아니라요.

하지만 잘 생각해보면, 이 골드바흐의 추측에서 힌트를 얻을 수 있어요.

먼저, 짝수중에서 네개의 처음으로 네개의 소수의 합으로 나타낼 수 있는 게 몇일까요?

"처음으로"라는 말은 네개의 소수의 합으로 나타낼 수 있는 것들중 가장 작다

 => 가장 작은 소수의 합으로 되어있다. 

=> 가장 작은 소수는 2이다.

그럼 2가 4번 있으면 되니, 2 + 2 + 2 + 2해서 8이겠네요.

네. 임의의 자연수중에서, "처음으로" 네개의 소수의 합으로 표현될 수 있는 자연수는 8입니다.

8미만의 수들은 가능할까요? 네. 가장 작은 짝수 소수인 2로만 이루어져 있기때문에 이보다 더 작을 수는 없습니다. 

그러므로 우리는 문제를 하나 풀었어요. 

첫째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다.

네. 그럼 임의의 자연수가 들어오면, 그것이 8보다 작은지 체크하고, 작으면 -1을 출력해주면 되겠네요. 

자 그러면, 이 문제와 골드바흐의 추측을 어떻게 연관지어서 풀것이냐?

일단, 우리 초등학교? 중학교때 배운 짝수, 홀수개념을 생각해볼게요. 

짝수 =  짝수 + 짝수

짝수 = 홀수 + 홀수

홀수 = 홀수 + 짝수

이정도는 알고 계실거에요. 

그러면 만약에 임의의 자연수 (이제부터 들어오는 모든 자연수는 8이상이라고 가정하겠습니다.) 가 들어왔어요.

1. 그 자연수(A)가 짝수였다. - 1

=> 짝수였으므로 이 짝수는 짝수 + 짝수인 값일것이다. 

=> 골드바흐의 추측 : 【4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 】

=>(이제부터 들어오는 모든 자연수들은 8보다 크다고 했으니, 이 A를 구성하는 짝수들은 최소 4일것이므로 조건을 만족합니다.(두 소수의 합으로 나타난다 했을 때))

=> A =  짝수(->두 소수의 합으로 나타낼 수 있다.) + 짝수 (-> 두 소수의 합으로 나타낼 수 있다.)

=> A = 소수 + 소수  + 소수 + 소수. (즉 , 네 개의 홀수의 합)

2. 그 자연수(A)가 짝수였다. - 2

=> 짝수였으므로 이 짝수는 홀수 + 홀수일 수도 있다.

=> 그럼 가장 작은 홀수 소수는 무엇일까요? 네. 3입니다.

=> 최초로 3의 합으로만 이루어지는 자연수는 무엇일까요? 

=> 네. 12입니다.

=> 12 = 3 + 3 + 3 + 3

==> 그럼 우리는 어떻게할지 결정해야합니다. 

==> 짝수 + 짝수는 최소가 8이지만, 홀수 + 홀수는 최소가 12이기때문에 우리는 짝수 + 짝수로 나타낼것입니다. 

왜냐하면 8이상, 12이하의 임의의 자연수가 들어왔을 때, 그것이 일단 네개의 소수의 합으로 나타내지면 되는거잖아요?

그러니까 짝수 + 짝수를 해야 8이상, 12이하의 자연수를 커버할 수 있는 것이죠.

3. 그 자연수(A)가 홀수였다. 

=> 홀수였으므로 이 홀수는, A = 홀수 + 짝수

=> 만약 9가 들어왔다면 9 = 4 + 5

=> 우리는 여기서 한가지 사실을 알아야합니다. 일단 홀수가 하나 정해지면, 나머지 짝수도 자연스럽게 정해진다는 것. 당연하죠?

=> 그럼 만약에 2 + 3의 합으로 나타내질 수 있는 5를 무조건 넣으면 나머지 짝수는, 들어온 임의의 자연수 - 5일 것이며, 그 수는 짝수일것입니다. 또한, 그 수에서 5를 빼도, 8이상의 가장 작은 홀수는 9이고, 5를 빼도 4가 남기때문에 골드바흐의 추측이 성립되게 됩니다. 

=> 그럼, 골드바흐의 추측에 의해서  【4 이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 】

=> 만약 9라면, 2와 3의 합으로 나타낼 수 있는 5를 9에서 빼주고, 9-5인 4를 다시 골드바흐의 추측에 의해서 두 소수의 합으로 나타내면 되겠죠.

=> 9 = 2 + 3 + 2 + 2

위 논리의 의해서 자연수 A가 짝수일때도 결정할 수 있습니다. 짝수에서 짝수를 빼면 짝수가 남기 때문이죠.

그렇다면, 우리는 2 + 2를 먼저 정해놓고, A - 4의 값을 골드바흐의 추측에 의해서 다시 두 소수의 합으로 나타낼 수 있습니다.

그렇다면 모든 로직은 완성됐어요.

1. 임의의 자연수(A)를 받는다.

2. 이 수가 8이상인지 체크한다.

3. 8미만이라면 -1을 리턴한다.

4. 8이상이라면 이 수가 홀수인지, 짝수인지 판단한다.

5. 짝수라면 2 + 2를 고정하고 이 수에서 4를 빼준다.

6. 홀수라면 2 + 3을 고정하고 이 수에서 5를 빼준다.

7. 나머지 두 수를 찾으려면, 에라토스테네스의 체가 필요하다 -> 일일이 찾으면 시간초과가 날 수 있음. 입력 범위가 백만까지이므로.

8. 에라토스테네스를 탐색하면서 나머지 두 소수를 찾는다. 동시에 A-(찾은 소수)가 소수이면 두 소수를 찾은 것이다.

이 것을 Swift 코드로 나타내면, 

import Foundation

var num = Int(readLine()!)!
var prime = [Int](repeating :0 ,count:1000001)
if num < 8 {
    print("-1")
    exit(1)
}


if num%2 == 0 {
    print("2 2", terminator:" ")
    num -= 4
}
else {
    print("2 3", terminator:" ")
    num -= 5
}

for i in stride(from: 2, through: num, by: 1){
    if prime[i] == 0{
        for j in stride(from: i*i, through: num, by: i){
            prime[j]=1
        }
    }
}
for i in stride(from: 2, through: num, by: 1){
    if prime[i] == 0 && prime[num-i]==0{
        print(i, num-i)
        break
        
    }
}

이렇게 되겠네요ㅎㅎ 알고리즘 공부할 때 굉장히 재밌게 푼 문제에요 :)

도움이 되었으면 좋겠네요.