[BOJ] 6588. 골드바흐의 추측

BaekJoon 6588. 골드바흐의 추측

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

[문제 접근]

에라토스테네스의 체를 응용해서 풀면 되는 문제다

처음에는 2중 for문으로 i +j == N을 해서 풀었더니 시간초과가 났다.

 

N-i를 해서 소수 판별을 같이 해서 하결하면 되는 문제였다.

근데 끝났는지 안 끝났는지 판별하는 boolean도 안 해주고 prime 배열을 while문 안에 같이 돌려줘서 오답과 메모리초과의 콜라보로 런타임 에러가 났다.

 

boolean flag를 해주고 prime배열을 위로 빼면서 범위 값을 정해줬다.

근데 또 배열 값의 범위롤 1000000이 아닌 100000으로 넣어서 런타임 에러가 났다

 

flag와 prime 배열을 수정하고 나니 성공했다....

 

 

 

 

 

 

 

 

 

 

[코드]

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

public class Main_6588 {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		boolean[] prime = new boolean[1000000+1]; //소수 판별 배열
		for (int i = 2; i < prime.length; i++) {
			for (int j = 2; i*j < prime.length; j++) {
				prime[i*j] = true; //소수가 아니면 true, 소수이면 false임
			}
		}

		prime[0] = true;
		prime[1] = true;

		while (true) {
			int N = Integer.parseInt(br.readLine());
			boolean flag = false; //계산 가능 판별
			
			if (N == 0) {
				break;
			}

			for (int i = 2; i <= N/2; i++) {
				if (!prime[i] && !prime[N-i]) { //i와 N-i가 소수이면
					System.out.println(N + " = " + i + " + " + (N-i));
					flag = true;
					break;
				}
			}
			if (!flag) { //답이 없으면
				System.out.println("Goldbach's conjecture is wrong.");
			}
		}

	}
}