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

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

https://www.acmicpc.net/problem/1644

https://github.com/citytexi/daily/pull/22

May/15 by citytexi · Pull Request #22 · citytexi/daily

---

문제

• 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
  • 3 : 3 (한 가지)
  • 41 : 2 + 3 + 5 + 7 + 11 + 13 = 11 + 13 + 17 = 41 (세 가지)
  • 53 : 5 + 7 + 11 + 13 + 17 = 53 (두 가지)
• 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.
• 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다.
• 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3 + 5 + 5 + 7과 같은 표현도 적합하지 않다.
• 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

---

입력

• 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

---

출력

• 첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

---

풀이

import kotlin.math.sqrt

private class Solution1644 {

    fun solution(num: Long): Long {
        val primeSum = getPrimeSum(num.toInt())
        var result = 0L
        var left = 0
        var right = 0

        while (right < primeSum.size) {
            val sum = primeSum[right] - primeSum[left]

            when {
                sum == num -> {
                    result += 1
                    left += 1
                    right += 1
                }
                sum < num -> right += 1
                else -> left += 1
            }
        }

        return result
    }

    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]) {
                continue
            }

            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
    }

}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    bw.append("${Solution1644().solution(br.readLine().toLong())}\n")
    bw.flush()

    br.close()
    bw.close()
}