[백준 6588번] [Kotlin] 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

난이도 : 실버 1
태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

 

 

설명

 

 

골드바흐 추측은

 

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

 

라는 추측입니다.

아직 수학적으로 증명되지 않았기에 추측이라고 불립니다.

 

4보다 큰 짝수를 두 홀수 소수의 합으로 나타낼 수 있을 경우,

두 소수의 차이가 가장 큰 두 수를 출력,

나타낼 수 없을 경우 "Goldbach's conjecture is wrong."를 출력합니다.

 

IBM에서 4부터 400경까지 다 넣어봤지만, 성립되지 않는 수는 없었다하네요.

물론 성립되지 않는 수는 없었다일 뿐, 수학적 증명은 아니였기 때문에 아직 추측이라 불립니다.

적어도 이 문제의 경우에는 "Goldbach's conjecture is wrong."를 출력할 일은 없겠네요.

 

해당 문제의 경우, 매 번 소수를 구하게 될 경우 시간 초과가 날 것이 뻔하기에,

에라토스테네스의 채가 유용하게  쓰일 것 같습니다.

 

 

 

소스코드

fun main() = with(System.`in`.bufferedReader()) {
    val arr = BooleanArray(1000001) { true }
    arr[0] = false
    arr[1] = false
    for (i in 2 until arr.size) {
        if (arr[i]) {
            for (j in i * 2 until arr.size step i) {
                arr[j] = false
            }
        }
    }

    while (true) {
        val n = readLine().toInt()
        if (n == 0) break
        var left = 3
        var right = n - 3

        while (left <= right) {
            if (arr[left] && arr[right]) {
                println("$n = $left + $right")
                break
            }
            left += 2
            right -= 2
        }
    }
}

 

 

에라토스테네스의 채를 통해 3부터 1000000까지 모든 소수를 구해놓고,

3, n - 3 부터 시작하여

left는 2씩 증가, right는 2씩 감소하면서 합이 n이 되는 홀수 소수를 찾으면 됩니다.

 

42의 경우,

3 + 39 = 42 지만 39는 소수가 아니므로 left는 2 증가, right는 2 감소합니다.

5 + 37 = 42, 5와 37 모두 소수입니다. a, b가 모두 소수인 경우를 찾았네요.

 

 

 

후기

골드바흐 추측은 페르마의 정리, 4색 문제, 리만 가설 등과 함께 수학계 난제 중 하나로 불립니다.

4색 문제의 경우 지도의 모든 나라를 칠하는데 4가지 색 만으로 가능한가? 라는 문제로,

컴퓨터를 사용해 4가지 색만으로 지도의 모든 나라를 칠하는 것이 가능하다는 게 증명되었으나,

골드바흐 추측의 경우엔 수는 무한하기 때문에 컴퓨터를 사용한 증명은 불가능합니다.

IBM이 한 것 처럼 '1부터 400경 까지는 성립이 되더라' 정도죠.

하루 빨리 소수의 비밀이 풀리는 날이 왔으면 좋겠네요.