[Swift] 백준 6588 - 골드바흐의 추측

문제 링크

이전에 배운 '에라토스테네스의 체'를 이용하여
범위 안의 숫자들의 소수를 판별하고,
소수들 중에서 덧셈 쌍을 구하면 되는 문제이다.

풀이는 쉬운데 시간초과가 많이 나서 애를 먹었다ㅠ

먼저 처음엔 다음과 같이 풀었다.

시간초과된 풀이

import Foundation

var numArray = [Int]()

func primeNum(x:Int) {
    numArray = Array(repeating: 0, count: x+1)
    
    for i in 2...x {
        numArray[i] = i
    }
    
    for i in 2...x {
        if numArray[i] == 0 { continue }
        
        for j in stride(from: i+i, through: x, by: i) {
            numArray[j] = 0
        }
    }
}


func primePair(x:Int) {
    
    for i in 3...x {
        
        if numArray[i] != 0 {
            let m = x - numArray[i]
            if numArray.contains(m) {
                print("\(x) = \(numArray[i]) + \(m)")
                break
            }
        }

    }
}

while true {
    let n = Int(readLine()!)!
    primeNum(x: n)
    primePair(x: n)
}

• 입력받은 숫자 범위 안에서
  • primeNum함수를 사용하여 소수를 판별(에라토스테네스의 체 이용)
  • primePair함수를 사용하여 소수 쌍을 출력

테스트케이스들은 다 통과하지만, 시간초과가 났다ㅠ
두 함수를 하나로 합쳐보기도하였고,
숫자를 받을 때 소수를 판별하는 것이 아니라 테스트 케이스(1000000)내의 소수 판별을 미리 해놓고 출력하는 방식도 시도해 보았으나 시간초과를 면하지 못했다..ㅠ

그래서 다른 분들 풀이를 참고하여
배열에 Index값을 넣지 않고, true/false로 소수를 판단하도록 하였다

import Foundation

let testCase = 1000000
var numArray = Array(repeating: true, count: testCase+1)

for i in 2...testCase {
    if numArray[i] == false { continue }

    for j in stride(from: i+i, through: testCase, by: i) {
        numArray[j] = false
    }
}

while true {
    let n = Int(readLine()!)!
    
    if n == 0 { break }
    
    for i in 3...n {
        if numArray[i] {
            let m = n - i
            if numArray[m] {
                print("\(n) = \(i) + \(m)")
                break
            }
        }
    }
}

겨우 통과가 되었다...😱