[Kotlin] 백준 1644 : 소수의 연속합

문제 링크

1644번: 소수의 연속합

---

문제 해설

사용 알고리즘 : 에라토스테네스의 체, 누적합과 부분합, 투 포인터

N이 최대 4,000,000이기 때문에 단순 이중 반복문으로 소수 판정을 하면 시간초과가 발생한다. 따라서 에라토스테네스의 체를 사용하여 소수를 판정해야 한다.(코드의 26~35번째 줄)

 

N 이하의 모든 소수를 판정했다면 이제 N이 소수들의 합으로 나타낼 수 있는지 확인해야 한다. 그런데 문제에서 '연속된 소수의 합'으로 나타낼 수 있는 경우의 수를 구하라는 언급이 있기 때문에 누적합과 투 포인터를 이용한 부분합을 사용하여 이를 효율적으로 구할 수 있다.

 

소수를 판별한 후 소수의 리스트를 반환하지 말고 소수들의 누적합 리스트를 반환하게 한다. 이 때, 누적합을 수월하게 구하기 위해 리스트의 첫 값은 0으로 세팅하고 더해준다.(코드의 37~40번째 줄)

 

연속된 소수의 누적합을 구했으니 마지막으로 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하면 된다. 이는 투 포인터로 간단히 구할 수 있다. 두 개의 포인터를 이동시켜가면서 부분합이 N보다 작다면 우측 포인터를, N보다 크다면 좌측 포인터를, N과 같다면 두 포인터 모두 우측으로 이동시켜가면서 경우의 수를 더해주면 된다.

Code

import kotlin.math.sqrt

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toLong()
    val primeSum = getPrimeSum(n.toInt())
    var count = 0
    var left = 0
    var right = 0

    while (right < primeSum.size) {
        val sum = primeSum[right] - primeSum[left]
        if (sum == n) {
            count++
            left++
            right++
            continue
        }
        if (sum < n) right++
        else left++
    }

    println(count)
}

private fun getPrimeSum(n: Int): List<Long> {
    val isPrime = BooleanArray(n + 1) { true }
    val sqrt = sqrt(n.toDouble()).toInt()
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..sqrt) {
        if (isPrime[i]) {
            for (j in i * i..isPrime.lastIndex step i) isPrime[j] = false
        }
    }

    val resultList = mutableListOf(0L)
    for (i in isPrime.indices) {
        if (isPrime[i]) resultList.add(resultList.last() + i)
    }

    return resultList
}