알고리즘 문제(Swift) - 백준 17103 (골드바흐 파티션)

www.acmicpc.net​

 

 

우선 최대 1,000,000까지의 정수 N을 입력 받기 때문에

에라토스테네스의 체 알고리즘을 이용하여 1,000,000까지의 소수를 판별하고

각 테스트케이스 별로 2부터 N/2까지 돌면서 합으로 이루어진 두 수가 소수인지 확인

 

example)

N = 6일 때, (3, 3)으로 이루어진 조합 1개

N = 8일 때, (3, 5)로 이루어진 조합 1개

N = 10일 때, (3, 7), (5, 5)로 이루어진 조합 2개

N = 12일 때 (5, 7)로 이루어진 조합 1개

 

 

let maxNum = 1000000 // N의 최대 값
var isPrime = Array(repeating: true, count: maxNum + 1)
isPrime[0] = false
isPrime[1] = false

for i in 2...maxNum { // 에라토스테네스의 체 알고리즘 사용하여 1,000,000까지 소수 판별
    if !isPrime[i] { continue }
    for j in stride(from: i * i, through: maxNum, by: i) {
        isPrime[j] = false
    }
}

func solution(N: Int) {
    var count = 0
    for i in 2...N/2 {
        if isPrime[i] && isPrime[N - i] { // 합으로 이루어진 두 수가 소수인지 확인
            count += 1
        }
    }
    print(count)
}

// 테스트케이스 반복
let T = Int(readLine()!)!
for _ in 0..<T {
    let N = Int(readLine()!)!
    solution(N: N)
}

/*
 6 - 3, 3
 8 - 3, 5
 10 - 3, 7 / 5, 5
 12 - 5, 7
 100 - 3, 97 /
 */