[6588] 골드바흐의 추측

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

풀이

소수 판별 문제이다. 문제를 보고서 소수 배열과 투 포인터를 사용하여 풀이를 제출했으나 시간 초과가 나왔다.

문제를 해결하기 위해서는 소수 배열의 작은 숫자부터 n의 차를 구한 수를 소수인지 판별하는 방법으로 해결해야 한다는 게시글을 보고서 다시 제출하였더니 통과했다.

 

시간 초과 코드

import Foundation

var numbers = Array(repeating: true, count: 1000001)
var primes = [Int]()
for i in 0..<1000001{
    if i <= 1{
        numbers[i] = false
        continue
    }
    if numbers[i]{
        if i != 2{
            primes.append(i)
        }
        for k in stride(from: i+i, to: 1000001, by: +i){
            numbers[k] = false
        }
    }
}

while let input = readLine(){
    let n = Int(input)!
    if n == 0{ break }
    
    var flag = false
    var start = 0
    var end = primes.count-1
    while start < end{
        let sum = primes[start] + primes[end]
        if sum > n{
            end -= 1
            continue
        }else if sum == n{
            flag = true
            break
        }else{
            start += 1
        }
    }
    if flag{
        print(n,"=",primes[start],"+",primes[end])
    }else{
        print("Goldbach's conjecture is wrong.")
    }
}

 

해결 코드

import Foundation

var primes = Array(repeating: true, count: 1000001)

for i in 0..<1000001{
    if i <= 1{
        primes[i] = false
        continue
    }
    if primes[i]{
        for k in stride(from: i+i, to: 1000001, by: +i){
            primes[k] = false
        }
    }
}

while let input = readLine(){
    let n = Int(input)!
    if n == 0{ break }
    
    var flag = false
    for i in 3..<1000001{
        if primes[i]{
            let chk = n-i
            if primes[chk]{
                flag = true
                print(n,"=",i,"+",chk)
                break
            }
        }
    }
    if !flag{
        print("Goldbach's conjecture is wrong.")
    }
}

 

심지어 문제를 풀고나서 알아낸 점은 같은 소수의 구성으로도 n을 만들 수 있다면 정답이 될 수 있다는 것이다. 투 포인터를 사용한 코드를 적을 때에 당연히 서로 다른 소수라는 가정을 한 채로 작성했었다. 대표적인 예시가 6을 입력할 경우 투 포인터를 사용한 코드는 불가능한 조합이라는 결과를 출력하지만, 통과했던 코드는 3 + 3 조합을 출력하게 된다.