백준 9020번 골드바흐의 추측 - SWIFT

문제

---

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

 

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

 

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

 

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

 

문제 링크

9020번: 골드바흐의 추측

 

 

풀이

---

`n`은 짝수 이므로, 2로 나누면 나누어 떨어진다.

 

2로 나눈 수를 변수 `a`와 `b`에 2로 나눈 수를 하나씩 나누어준다.

 

그리고 `a`를 작은 수라고 하고 `b`를 큰 수라고 지정해놓고,

작은 수는 초기값으로부터 계속 -1,

큰 수는 초기값으로부터 계속 +1을 해주면서

`a`와 `b`가 둘 다 소수인지 검사하면 된다.

 

`a`와 `b`는 `n`보다 작은 모든 수가 될 수 있으므로, 짝수 `n`보다 작은 모든 소수를 알면 문제는 쉽게 풀린다.

 

그렇다면 핵심은 모든 소수를 아는 것이 되는데, 범위 내의 모든 소수를 구하는 것은 에라토스테네스의 체를 이용하면 쉽게 구할 수 있다.

 

아래의 글에 소수의 단일 판정과 범위 판정에 대한 설명이 있으니 참고하여 문제를 해결하면 된다.▼

간단한 수학(+ 약간의 정수론)

 

 

프로그램 동작

1. `n`까지의 소수를 모두 구한다.
2. `n`을 2로 나눠서 `a`와 `b`에 넣는다.
3. `a`와 `b` 둘 다 소수인지 체크해본다.
   3-1. 둘 다 소수라면 `a`, `b`출력과 함께 종료한다.
4. 둘 중 하나라도 소수가 아닐 경우 `a`는 -1, `b`는 +1을 해서 3번을 반복한다.

 

Swift 코드

---

let T = Int(readLine()!)!
var prime = Array(repeating: true, count: 10001)

func primeNum() {
    prime[0] = false
    prime[1] = false
    for i in 2..<10000 {
        for j in stride(from: i * 2, to: 10000, by: i) {
            prime[j] = false
        }
    }
}

func goldbach(_ a: Int, _ b: Int, _ c: Int) {
    if a < 4 || a > 10000 || a % 2 != 0 {
        return
    } else {
        if prime[b] == true && prime[c] == true {
            print(b, c)
        } else {
            goldbach(a, b - 1, c + 1)
        }
    }
}

primeNum()

for _ in 0..<T {
    let tmp = Int(readLine()!)!
    goldbach(tmp, tmp / 2, tmp / 2)
}