백준 9020 골드바흐의 추측
23 Jun 2021https://www.acmicpc.net/problem/9020
골드바흐의 추측이란 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이 때 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 부를 때 2보다 큰 짝수 n에 대해서 골드바흐 파티션을 출력하는 문제이다. 만약 파티션이 여러가지일 경우 두 소수의 차이가 가장 작은 것을 출력한다.
여러개의 테스트 케이스가 주어지기 때문에 범위내의 숫자에 대해 소수 여부를 미리 파악하고 있으면 좋겠다는 생각이 든다. 따라서 에라토스테네스의 체를 활용해 숫자 10000까지 소수 여부를 확인해주자. 우리는 두 소수의 차이가 가장 작은 것을 출력하고 싶기 때문에 n/2부터 시작해서 하나는 1씩 감소시키고 하나는 1씩 증가시키면서 두 숫자 모두 소수일 경우를 찾아주면 된다. 소수 여부는 에라토스테네스의 체로 만들어둔 배열을 확인한다.
- 전체 코드
readLine()
var arr = [Bool](repeating: true, count: 10001)
for i in 2...10000 {
if !arr[i] {continue}
for j in stride(from: 2*i, through: 10000, by: i) {arr[j] = false}
}
while let line = readLine() {
var compare1 = Int(line)!/2
var compare2 = Int(line)!/2
while compare1 > 1 {
if arr[compare1] && arr[compare2] {
print("\(compare1) \(compare2)")
break
}
else {
compare1 -= 1
compare2 += 1
}
}
}