백준 6588번 골드바흐의 추측 자바

골드바흐의 추측 문제 보러가기

문제 설명

자바 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static boolean[] isPrimeNumbers=new boolean[1000001];
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        isPrimeNumbers[2]=true;
        getPrimeNumber();

        while (true){
            int testCase=Integer.parseInt(br.readLine());
            boolean isWrong=true;
            if(testCase==0){
                System.out.print(sb.toString());
                return;
            }

            for(int i=3; i<=testCase/2;i+=2){
                if(isPrimeNumbers[i]&&isPrimeNumbers[testCase-i]){
                    sb.append(testCase+" = "+i+" + "+(testCase-i)+"\n");
                    isWrong=false;
                    break;
                }
            }
            if(isWrong) sb.append("Goldbach's conjecture is wrong.\n");

        }
    }

    public static void getPrimeNumber(){
        for(int i=3;i<isPrimeNumbers.length;i+=2){
            isDivided(i);
        }
    }

    public static void isDivided(int number){//소수로 나누었을때 떨어지는지 확인
        int x=(int)Math.sqrt(number);
        for (int i=1;i<number;i++) {
            if(isPrimeNumbers[i]){
                if(i>x){
                    isPrimeNumbers[number]=true;
                    return;
                }
                if(number%i==0) return; //나누어떨어지면 소수가 아님
                }
        }
    }

}

문제 풀이

이번 문제는 테스트케이스가 최대 1000000 이므로 1000000크기의 boolean 배열로 잡아 소수면 true 로 잡은 후

testCase = i +(testCase-i) 를 이용하여 i값을 3 부터 +2씩하여 test반복하여 체크하면 됩니다.

• boolean 배열의 소수를 true로 체크합니다..
• testCase = i +(testCase-i) 를 이용하여 i값을 3 부터 +2씩하여 반복하여 i값과 (testCase-i) 가 true일때 출력합니다.