Kotlin 🍬 백준 15단계 :: 17103 번

골드바흐 파티션

문제   |

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

입력   |

  첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

 

출력   |

  각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

 

 

풀이  |

  입력받은 N을 2부터 N/2까지 for문을 돌려 해당 값이 소수이면, N에서 해당 값을 뺀 수가 소수인지 boolean 값을 구한다. 만약, 둘 다 소수이면 count의 갯수를 1 늘린다.

 

 

답안  |

fun main() {
    val T = readLine()!!.toInt()
    repeat(T) {
        val N = readLine()!!.toInt()
        println(countGoldbachPartitions(N))
    }
}

fun countGoldbachPartitions(N: Int): Int {
    var count = 0
    for (i in 2..N / 2) {
        if (isPrime(i) && isPrime(N - i)) {
            count++
        }
    }
    return count
}

fun isPrime(num: Int): Boolean {
    if (num == 1) {
        return false
    } else if (num == 2) {
        return true
    } else {
        for (i in 2..(Math.sqrt(num.toDouble())).toInt()) {
            if (num % i == 0) {
                return false
            }
        }
        return true
    }
}

 

^ 시간초과된 코드...

 

이전 문제에서 다루었던 에라토스테네스의 체 알고리즘 사용

fun main() {
    val T = readLine()!!.toInt()
    val limit = 1000000 // 주어진 최대 N 값
    val primes = sieveOfEratosthenes(limit) // 소수 리스트를 미리 구한다.
    repeat(T) {
        val N = readLine()!!.toInt()
        println(countGoldbachPartitions(N, primes))
    }
}

fun sieveOfEratosthenes(limit: Int): BooleanArray {
    val sieve = BooleanArray(limit + 1) { true }
    sieve[0] = false
    sieve[1] = false
    var p = 2
    while (p * p <= limit) {
        if (sieve[p]) {
            var i = p * p
            while (i <= limit) {
                sieve[i] = false
                i += p
            }
        }
        p++
    }
    return sieve
}

fun countGoldbachPartitions(N: Int, primes: BooleanArray): Int {
    var count = 0
    for (i in 2..N / 2) {
        if (primes[i] && primes[N - i]) {
            count++
        }
    }
    return count
}