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

백준 1644 - 소수의 연속합 문제.
N 이하의 모든 연속적인 소수를 구하고 가변 슬라이딩 윈도우를 통해 정답을 도출해내는 문제이다.

과거에 N 이하의 소수들을 구하는 문제에서 에라토스테네스의 체 라는 소수를 찾는 방법을 알게 되어, 이를 활용하려고 하였는데 이보다 더 좋은 방법은 없을까 싶어 찾아보니 O(N log log N) 인 에라토스테네스의 체 보다 빠른 오일러의 체 O(N) 이 존재한다고 하여 이를 활용하였다.

처음에는 오일러의 체를 이용하였으나, 낮은 캐시 히트율과 IntArray 사용 이유로 에라토스테네스의 체가 더 빠르게 처리된다는 것을 알고 변경하였다.

풀이 1. 에라토스테네스의 체

fun `1644-소수의 연속합`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val primeList = mutableListOf<Int>()
    val isPrime = BooleanArray(n + 1){ true }

    isPrime[0] = false
    isPrime[1] = false

    for(i in 2 .. kotlin.math.sqrt(n.toDouble()).toInt()){
        if(isPrime[i]){
            for(j in i + i .. n step i){
                isPrime[j] = false
            }
        }
    }

    for(i in isPrime.indices){ if(isPrime[i]) primeList.add(i) }

    var start = 0
    var end = 0
    var currentSum = 0
    var count = 0
    val limit = primeList.size - 1

    while (true){
        when {
            // 오름차순인 소수 배열이므로 currentSum 이 N 보다 크거나 같으면 start 만큼 빼주고 start 를 늘려준다.
            currentSum >= n -> {
                if(currentSum == n) count++
                currentSum -= primeList[start]
                start++
            }
            // currentSum 이 n 보다 작고 end 가 limit 보다 큰 경우는 이미 끝까지 순회하였다는 의미이다.
            end > limit -> break
            // N 보다 작으므로 currentSum 에 prime[end] 를 추가해주고 end 를 늘려준다.
            else -> {
                currentSum += primeList[end]
                end++
            }
        }
    }

    bw.write(count.toString())
    bw.flush()
    bw.close()
    br.close()
}

풀이 2. 오일러의 체

/*
연속된 합 -> 슬라이딩 윈도우
* */
fun `1644-소수의 연속합`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val primeList = mutableListOf<Int>()
    val numberArr = IntArray(n + 1){ it }

    // n 이하의 모든 소수를 확인하기 위해 순회한다.
    for(i in 2 .. n){
        // numberArr[i] 가 i 라면 이전 소수값 판별에서 처리되지 않은 값이므로 소수가 맞다.
        if(numberArr[i] == i) primeList.add(i)

        // 소수로 판별된 리스트를 순회한다.
        for(p in primeList){
            // numberArr[i] 에 등록된 값이 현재 값보다 큰 경우 = 소인수 적용된 것이므로 종료.
            // p * i 가 N 보다 큰 경우 = 값을 벗어난 것이므로 종료
            if(p > numberArr[i] || p * i > n) break
            // i * p = 소인수 (가장 작게 나눠지는 값) 이다.
            numberArr[i * p] = p
        }
    }

    var start = 0
    var end = 0
    var currentSum = 0
    var count = 0
    val limit = primeList.size - 1

    while (true){
        when {
            // 오름차순인 소수 배열이므로 currentSum 이 N 보다 크거나 같으면 start 만큼 빼주고 start 를 늘려준다.
            currentSum >= n -> {
                if(currentSum == n) count++
                currentSum -= primeList[start]
                start++
            }
            // currentSum 이 n 보다 작고 end 가 limit 보다 큰 경우는 이미 끝까지 순회하였다는 의미이다.
            end > limit -> break
            // N 보다 작으므로 currentSum 에 prime[end] 를 추가해주고 end 를 늘려준다.
            else -> {
                currentSum += primeList[end]
                end++
            }
        }
    }

    bw.write(count.toString())
    bw.flush()
    bw.close()
    br.close()
}

후기

과거 소수 판별을 위한 방법으로는 에라토스테네스의 체밖에 몰랐고, 나중에 이에 대해 글을 작성하려고 하였는데 오일러의 체 방식이 O(n) 이 걸린다는 것을 깨닫고, 이것을 이용해보았다.

다만 이론적으로 더 빨랐던 오일러의 체 방식이 실제로는 훨씬 느리게 처리되어, 왜 그런가 알아보니 계산이 더 복잡해지면서 CPU 캐시 미스가 발생하여 더 느린 시간이 걸린다는 것을 알았다.

이론적으로는 에라토스테네스의 체의 경우 O(N log log N) 이 걸리고, 오일러의 체의 경우 O(n) 의 시간이 걸린다는데, 이론일 뿐 실전에서는 다르다는 것을 알았다.

앞으로는 캐시 히트, 미스에 대해서도 생각하며 풀어야할 것 같고, 슬라이딩 윈도우에 관해서는 아직도 조금 헷갈리는 감이 있어 조금 더 풀어봐야겠다.