21. 6588번 골드바흐의 추측

짝수인 값을 입력받으면 해당 짝수를 홀수인 소수의 합으로 만들수 있는지에 대한 문제이다.

조금전 풀었던 소수 구하기의 에라토스 테네스의 체를 이용해 풀어볼 생각이다.

 

우선 에라토스 테네스의 체를 이용해 문제에서 제공하는 6부터 100만 까지의 수에서 소수를 추출해 낸다.

이후 해당 소수들로 입력받은 짝수가 완성될 수 있는지를 판별하고

가능하다면 해당 수들을 출력하려고 한다.

 

내가 생각한 키포인트는 n(입력받은 짝수) = a(소수) + b(소수) 라는점

여기서 짝수는 몰라도 소수는 우리가 판별할 수 있다. 에라토스테네스의 체를 이용하여 소수가 아닌 값은 모조리 true로 바꿔줄 것이기 떄문

이말을 듣고 위 조건을 보면 n = false + false 라는 형태가 눈에 보일것 이다. 이걸로는 해결을 못하겠지만 false를 반대로 넘겨보자

n - false = false 두 항 모두 우리가 알고있는 false값을 가지게되고 비로소 알아보기 쉬운 조건이 나오게된다.

 

즉 우리는 입력받은 짝수 n 을 우리가 판별한 소수 a,b를 이용해 n-a , n-b 했을때 나오는 결과값이 false인 수 면 출력하면 된다 라는 결과가 나온다.

 

 

1. 에라토스테네스의 체를 이용한 소수 판별 ( 100만까지 ) 해당 소수들 소수 배열에 저장

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

public class training2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[] arr = new boolean[1000001];
        
        arr[0] = true;
        arr[1] = true;

        for (int i = 2; i <= b; i++) {
            if (arr[i] == true) {
                continue;
            }
            for (int j = i + i; j <= 1000000; j = j + i) {
                arr[j] = true;
            }
        }
    }
}

false = 소수

 

3. 

 

3. 입력받은 n - 소수[i] = false 면 해당 배열들 넣어서 출력 

while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0)
                break;

            for (int i = 0; i < prime.size(); i++) {
                if (arr[n - prime.get(i)] == false) {
                    System.out.println(n + " = " + prime.get(i) + " + " + (n - prime.get(i)));
                    break;
                } else {
                    System.out.println("Goldbach's conjecture is wrong.");
                    break;
                }
            }
        }

 

코드전문

package com.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class training {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[] arr = new boolean[1000001];
        ArrayList<Integer> prime = new ArrayList<>();

        arr[0] = true;
        arr[1] = true;

        for (int i = 2; i <= 1000000; i++) {
            if (arr[i] == false) {
                prime.add(i);
            }
            for (int j = i + i; j <= 1000000; j = j + i) {
                arr[j] = true;
            }
        }

        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0)
                break;

            for (int i = 0; i < prime.size(); i++) {
                if (arr[n - prime.get(i)] == false) {
                    System.out.println(n + " = " + prime.get(i) + " + " + (n - prime.get(i)));
                    break;
                } else {
                    System.out.println("Goldbach's conjecture is wrong.");
                    break;
                }
            }
        }

    }

}

 

출력은 정상적이나

결과는 런타임에러가 뜬다.

물론 코드에서 클래스명을 Main으로 바꾸어 실행한 결과이다.