[Algorithm] 백준 - 1644번 소수의 연속합 (Swift)

문제 소개

자연수 N 이 주어지면 N 보다 작은 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제.
 

문제 풀이

소수는 에라토스테네스의 체를 통해서 구했고, 연속된 소수의 합은 투포인터 알고리즘을 사용하였다.

import Foundation

let n = Int(readLine()!)!

// 입력값이 1일경우 빠른 처리
if n == 1 {
    print(0)
    exit(0)
}

// 에라토스테네스의 체
var isPrimeNumber = Array(repeating: true, count: n+1)
var primeNumber = [Int]()

let sqrtN = Int(sqrt(Double(n)))

for i in 2..<sqrtN+1 {
    if isPrimeNumber[i] {
        var j = 2
        while i * j <= n {
            isPrimeNumber[i*j] = false
            j += 1
        }
    }
}

for i in 2...n {
    if isPrimeNumber[i] {
        primeNumber.append(i)
    }
}

// 투포인터 알고리즘
var s = 0
var e = 0
var sum = primeNumber[0]
var answer = 0

while s < primeNumber.count && e < primeNumber.count {
    if sum == n {
        answer += 1
    }
        
    if sum > n {
        sum -= primeNumber[s]
        s += 1
    } else {
        e += 1
        if e < primeNumber.count {
            sum += primeNumber[e]
        }
    }
}

print(answer)

 

결과

문제없는 듯 하다.