[백준 6588, Java] 골드바흐의 추측

문제

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

풀이

1. 1부터 1,000,000까지 소수를 구한다(에라토스테네스의 체 이용)

2. 입력(num)으로 0이 나오기 전까지 반복문을 수행한다

   2-1 1번에서 구한 소수배열(isPrimeNum)을 순회(n)하면서 n, num-n이 모두 소수일때 반복문을 종료한다 

 

check

1. 에라토스테네스의 체의 시간복잡도는 nlog(log n)이다. 따라서 1,000,000인경우 근사값 778,151이 나온다. isGold의 경우 시간복잡도는 O(1000000) 이므로  두 시간복잡도를 더해도 1억이하이기떄문에 1초가 안된다( 확실하지는 않음) 

 

2. 시간복잡도를 알아야! 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static boolean[] isPrimeNum = new boolean[1000001];
    public static int[] goldNum = new int[2];
    
    public static void main(String[] args) throws  Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //1부터 1,000,000까지 소수 구하기
        Arrays.fill(isPrimeNum, true);
        eratos();


        int number = 0;
        while(true){
            number = Integer.parseInt(br.readLine().trim());
            if(number == 0){
                break;
            }
            else{
                if(isGoldNum(number)){
                    bw.write(number +" = "+goldNum[0]+" + "+goldNum[1]+"\n");
                }
                else{
                    bw.write("Goldbach's conjecture is wrong.\n");
                }
            }
        }
        bw.flush();

        br.close();
        bw.close();
    }
    public static boolean isGoldNum(int num){
        //4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
        for(int n = 3 ; n<isPrimeNum.length; n++){
            if(isPrimeNum[n] && isPrimeNum[num-n]){
                goldNum[0] =n;
                goldNum[1] = num-n;
                return true;
            }
        }
        return false;
    }

    public static void eratos(){
        for(int num = 2; num < isPrimeNum.length ; num++){
            if(isPrimeNum[num]){
                for(int n = 2; n*num <isPrimeNum.length ; n ++){
                    if(isPrimeNum[n*num]) isPrimeNum[n*num] =false;
                }
            }
        }
    }
}