[Swift] 백준 알고리즘 6588

let maxValue = 1000000
func sol() {
    var targetArr = Array(repeating: 0, count: maxValue + 1)
    var tempTargetArr = Array<Int>()
    for i in stride(from: 2, to: maxValue, by: 1) {
        if targetArr[i] == -1 {
            continue
        }
        tempTargetArr.append(i)
        for j in stride(from: i*2, to: maxValue, by: i) {
            targetArr[j] = -1
        }
    }

    while true {
        var leftInd = 0
        var rightInd = tempTargetArr.endIndex - 1
        let inputValue = Int(readLine()!)!
        if inputValue == 0 {
            break
        }
        var value = 0
        while leftInd <= rightInd {
            value = tempTargetArr[leftInd] + tempTargetArr[rightInd]
            if value > inputValue {
                rightInd -= 1
            }
            else if value < inputValue {
                leftInd += 1
            }
            else {
                print("\(inputValue) = \(tempTargetArr[leftInd]) + \(tempTargetArr[rightInd])")
                break
            }
        }
        if leftInd > rightInd {
            print("Goldbach's conjecture is wrong.")
        }
    }
}

sol()

개요 : 문제 풀이 방식

 

소수를 Arr에 쑤셔 넣고 -> leftInd와 rightInd를 통해 값을 구하려 함 -> 시간 초과

 

 

해결 : 아라토스테네체로 소수 배열 구하기 -> i와 inputvalue - i 가 둘 다 소수가 될 떄 값을 구하고 break

func sol2() {
    var targetArr = Array(repeating: 0, count: maxValue + 1)
    for i in stride(from: 2, to: maxValue, by: 1) {
        if targetArr[i] == -1 {
            continue
        }
        for j in stride(from: i*2, to: maxValue, by: i) {
            targetArr[j] = -1
        }
    }
    while true {
        let inputValue = Int(readLine()!)!
        if inputValue == 0 {
            return
        }
        for i in stride(from: 3, to: inputValue/2 + 1, by: 1) {
            if (targetArr[i] == 0 && targetArr[inputValue - i] == 0) {
                print("\(inputValue) = \(i) + \(inputValue - i)")
                break
            }
        }
    }
}
sol2()