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

문제

---

 

 

문제해결

---

- 에라토스테네스의 체를 활용하여 소수를 구한다, boolean 배열에서 소수는 false가 된다

- 홀수 소수만 사용하기 때문에 모든 짝수는 true로 바꾼다, 홀수 소수만 false가 된다

- 3부터 1000000까지 반복문을 돌면서 i가 홀수 소수이며 입력받은 num - i 가 홀수 소수일때는 추측이 성립한다

- b-a가 가장 큰걸 출력해야 하므로 가장 첫번째 것만 출력하고 반복문을 빠져나온다

- 추측이 성립 안될 경우 "Goldbach's conjecture is wrong."를 출력해야 하지만 그런 경우는 없는 듯 하다(flag 변수로 해주는 것이 좋다)

import java.util.Scanner;

public class B6588 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //소수 구하기
        boolean[] sosu = new boolean[1000001];
        sosu[0] = true;
        sosu[1] = true;
        for (int i = 2; i <= Math.sqrt(1000000); i++) {
            if (sosu[i]) continue;
            for (int j = i*i; j <= 1000000; j+=i) {
                sosu[j] = true;
            }
        }
        //홀수만 false로
        for (int i = 2; i <= 1000000; i+=2) {
            sosu[i] = true;
        }

        int num = 0;
        while ((num=sc.nextInt())!=0){
            for (int i = 3; i <= 1000000; i++) {
                if (!sosu[i] && !sosu[num-i]){
                    System.out.println(num + " = " + i + " + " + (num-i));
                    break;
                }
            }
        }
    }
}