백준 15711: 환상의 짝꿍

두 수의 합이 다른 두 소수의 합으로 표현할 수 있는가에 대한 문제다.

문제에서 A와 B의 범위는 1 이상이므로 합은 2, 3, 4, ...로 나올 수 있다.

 

이때 A+B가 2 또는 3이라면)

가장 작은 소수 2를 뺐을 때 나머지 0 또는 1이 소수가 아니므로 두 소수의 합으로 표현할 수 없다.

 

A+B가 4 이상의 짝수라면)

골드바흐의 추측*에 의해 '어지간한 수'까지는 두 소수의 합으로 표현할 수 있다.

* 수학적으로 엄밀한 증명이 이뤄지지는 않았지만, 우리 문제 범위에서는 영향이 없다.

 

A+B가 4 이상의 홀수라면)

2로 뺀 A+B-2가 소수라면 두 소수의 합으로 표현할 수 있고, A+B-2가 소수가 아니라면 두 소수의 합으로 표현할 수 없다.

예를 들어 19는 2+17의 쌍으로 표현할 수 있다. 하지만 23은 2+21에서 21이 합성수이므로 표현할 수 없다.

A+B가 홀수면서, A+B에 홀수의 소수를 뺀 결과가 2가 아닐 때, 반드시 짝수는 소수가 아니므로 두 소수의 합으로 표현할 수 없는 것이다.

따라서 A+B-2가 소수인지만 판명하면 되는 문제이므로, 10^12개의 입력 수에서 소수를 판정하면 된다.

이는 Miller-Rabin 판별법을 사용하면 간단하게 해결된다. Java, Kotlin을 사용한다면 BigInteger의 isProbablePrime 메소드를 사용해도 좋다.

 

마지막 경우의 수를 제외하고는 미리 상수시간에 해결해두고, 마지막 경우만 빠른 소수 판별법을 활용하도록 하자.

Miller-Rabin 소수 판별은 다른 문제에서도 많이 활용되니 미리 구현해두면 요긴하게 사용할 수 있다.