[백준] 1644번: 소수의 연속합 - Kotlin[코틀린]

문제

 

1644번: 소수의 연속합

 

---

풀이

 

 에라토스테네스의 체를 활용하여 소수 판정을 먼저 수행하고, 투 포인터를 이용하여 합이 입력받은 값이 되는 경우를 세어주면 된다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가며 소수를 구하는 방법이다. 다음의 그림을 보면 쉽게 이해할 수 있다.

이미지 출처 - 위키백과

 

 먼저 입력받은 범위까지의 소수를 구하고, 그 소수를 리스트에 저장한다. 이 리스트를 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다.

 

 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포인터를 뒤로 이동시킨다. 만약 end 포인터가 이미 배열의 끝까지 도달했다면 반복문을 종료한다. 누적 합이 찾으려는 값보다 크거나 같다면 start 포인터를 뒤로 이동시킨다. 찾으려는 값과 같을 때는 개수를 세어준다.

 

---

코드

 

import kotlin.math.*

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

    val num = br.readLine().toInt()
    var cnt = 0
    var tmp = 0
    var start = 0
    var end = 0

    val prime = BooleanArray(num+1) { true }
    for(i in 2 .. sqrt(num.toDouble()).toInt()) {
        if(!prime[i]) continue
        for(j in i*i..num step i) {
            prime[j] = false
        }
    }
    val list = mutableListOf<Int>()
    for(i in 2..num) {
        if(prime[i]) list.add(i)
    }

    while(true) {
        if(tmp>=num) {
            if(tmp==num) cnt++
            tmp -= list[start++]
        } else {
            if(end==list.size) break
            tmp += list[end++]
        }
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}