[백준 / BOJ] 네 개의 소수 - 1153 (Java)

문제 : https://www.acmicpc.net/problem/1153

 
임의의 자연수 N에 대해서, 해당 수를 4개 소수의 합으로 표현하는 문제이다.
4개의 소수 중, 중복인 수가 있을 수 있으며, 답이 여러가지인 경우가 있을 수 있다, 그 중 하나만 출력하면 된다.
 

풀이

1.
  문제의 4개의 소수를 'N을 구성하는 수'라고 하자. N을 구성하는 수는 모두 소수이므로, 우리는 자연수 중 어떤 수가 소수인지 알아야한다. 주어지는 N의 범위가 크기 때문에 에라토스테네스의 체를 이용해 N이하의 자연수 범위에서의 소수 여부를 저장하는 테이블을 구하자.
 
2. 
  문제에서 의도한 정석적인 풀이는 아닐 수 있지만, 필자는 골드바흐의 추측을 이용해 해결하였다. 골드바흐의 추측이란, '4이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다'는 추측이다. 아직 증명되지 않은 전설의 난제 중 하나이지만, 400경까지의 수에 대해 성립하는 것이 확인되었으며, 문제의 N이 100만을 넘지 않으므로, 해당 문제에 응용하기에 전혀 문제가 없다. (참고로, 골드바흐의 약한 추측 : '5보다 큰 모든 홀수는 세 소수의 합으로 나타낼 수 있다'는 증명되었다.)
 
3.
  골드바흐의 추측을 사용해 해당 문제를 해결하기 위해 거쳐야하는 단계가 있다. 바로 주어진 수 N을 짝수로 만드는 것, 이는 꽤나 간단하다. 짝수 = 짝수 + 짝수, 홀수 = 짝수 + 홀수 이므로,  N이 짝수라면 4 = 2 + 2를 빼주고, N이 홀수라면 5 = 2 + 3을 빼주면 된다. 이러면 벌써 4개의 소수 중 2개의 소수를 찾았다(2,2 or 2,3), 그리고 N - (4 or 5)는 짝수이므로 골드바흐의 추측에 의해 반드시 두개의 소수 합으로 표현할 수 있다. (단, N - (4 or 5)는 4 이상의 수여야 한다. 따라서 N < 8 인 경우 해가 없으므로 답은 -1이다)
즉, N이 짝수라면 N을 구성하는 수는 (2 2 X Y)
N이 홀수라면 N을 구성하는 수는 (2 3 X Y) 로 표현 가능하다!
 
4.
   K := N - (4 or 5) 로 정의하자, 이제 우리는 K를 구성하는 X Y를 찾기만 하면 된다. 이때 1번 과정에서 에라토스테네스의 체를 통해 얻은 소수 테이블을 참조하면 된다.  i 를 2부터 K / 2까지 증가시켜서 i, K - i가 둘 다 소수인 경우를 테이블을 통해 찾으면 된다. 골드바흐의 추측에 의해, 해는 반드시 존재한다.
 

소스코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        run(scanner.nextInt());
    }
    
   
    static  boolean pnDetector(int number){
        boolean pn = true;
        
        if(number==2){
            return true;
        }
        
        else if(number==1) return false;
        
        else{
            double root = Math.sqrt(number);
            for(int i=2; i<root+1; i++){
                if(number%i==0){ pn = false; break;}
                else pn=true;
            }
            return pn;
       }
    }
    
    
    static void run(int number){
    
        if(number < 8){
            System.out.println(-1);
            number=0;
        }
        
        else if(number%2 == 1){
            number -= 5;
            System.out.print("2 3 ");

        }
        
        else if(number%2 == 0){
            number -= 4;
            System.out.print("2 2 ");
        }
        
        if(number == 4) System.out.print("2 2");
        
        else if(number > 4)
            for(int i=3; i<number; i=i+2){
            if(pnDetector(i)&&pnDetector(number-i)){
                int lastPN = number-i;
                System.out.print(i+" "+lastPN);
            break;}
        }
    }
}

참고,
해당 소스코드는 에라토스테네스의 체를 사용하진 않았으며, 들어오는 수에 대해 소수 여부를 판정하는 함수를 구현했다. N이 하나만 주어지므로 미리 테이블을 구현하지 않아도 시간 안에 풀렸다.