백준 6588 - 골드바흐의 추측

 

-해결방법

 

1. 숫자 N을 입력 받고 N이하의 소수 중에서 만족하는 숫자를 찾는다

 

2  만족하는 숫자를 찾는 방법 

   

    2.1 2중 for문을 돌면서 전부 비교하기 -  N이하의 소수 중 가장 작은 소수와 가장 큰 소수를 더 해본다.

         -true -> a+b를 출력하고 break

         -false -> 다음으로 큰 소수를 ..그 다음 소수 반복 그래도 찾지 못하면, 그다음 작은 소수와 가장 큰 소수를 더 해본다.

     

int[] primeNumber // 2~M 이하의 소수를 담은 배열
for(int i=0; i<=primeNumber.length; i++){
    for(int j=primeNumber.length-1; j>=i; j--){
    	if(m - primeNumber[0] - primeNumber[j] == 0){
        	System.out.println(//);
            break;
        }
    }
}

이를 모든 테스트 케이스에서 반복하면 될 수 있다.

 

하지만 시간복잡도가 N^2에다가 테스트 케이스 까지 합치면, m*n^2으로 시간 복잡도가 구리다.

다른 방법을 생각해 봐야한다.

 

  2.2  M = 소수 a + 소수 b가 성립한다면, M - a  혹은 M -b의 결과는 소수 일 것이다. 이를 이용하면 훨씬 빠르게 검사할 수 있다.

 int index // 실제 저장된 소수 갯수 
 int[] primeNumber;//
 boolean[] checkprime; // 소수면 false 아니면 true
for(int i=0; i<index; i++){
	if(!checkprime[n-primeNumber[i]]) //출력
}

 

훨 간결하게 처리할 수 있다.

 

따라서 이를 적용한 전체 소스는 다음과 같다.

 

public class Main{
    
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        final int MAX = 1000000;
        boolean[] checkPrime = new boolean[MAX+1];
        int[] primeArr = new int[MAX];

        checkPrime[0] = checkPrime[1] =true;
        int counter =0;

        //에라토스테네스?
        for(int i=2;i<=MAX;i++){ //그냥 검사만 할꺼면, 루트max만 해도 되는데 숫자 넣을꺼면 다해라 (일단 해두기)
            if(checkPrime[i] == false){ //이처럼 큰 계산 한번에 할 수 있으면 해두는 게 좋다.
                primeArr[counter++] = i;
                for(int j=i*2;j<=MAX;j+=i)
                    checkPrime[j]=true;
            }
        }
        
        int t;
        while (true) {
            t=Integer.parseInt(br.readLine());
            if(t==0) break;
            //소수 찾기  n짝수 = a소수 +b소수 -- n-b = a 이므로 n-b가 소수여야함
            for (int i = 1; i < counter; i++) {
                if (checkPrime[t-primeArr[i]]==false){
                    bw.write(t +" = "+primeArr[i]+" + "+(t-primeArr[i])+"\n");
                    break;
                }
            }

        }

        bw.flush();
        bw.close();
       
    }
}