[Eric's 백준] 6588번 - 골드바흐의 추측 - Java

안녕하세요! Eric 입니다!

오늘 제가 풀어볼 문제는 골드바흐의 추측

백준 6558번 입니다.

이번 문제 역시 '소수'를 이용해서 문제를 풀어야하는데요,

 

이때 저는 소수를 구할때,

에라토스테네스의 체 를 이용해서 소수인지 판별을하고,

해당 내용을 이미 max값의 크기의 isPrime[] 배열에 넣은다음에

(미리 배열을 구해놓고 진행한 이유는, 만약 다른 수가 나올때마다 배열을 구해서 소수를 구하면 시간복잡도가 더 높아질거라고 생각해서 이렇게 진행하였습니다.)

 

isPrime[]이라는 배열을 이용해서 이미 완성된 소수의 모임에서

다시 for문을 통해서 돌면서

우리가 원하는 골드바흐의 추측 내용이 나오는

값을 출력하면 끝이 납니다!

출처 : 위키피디아

 

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	public class N6588 {
	static final int MAX = 1000000;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	boolean isPrime[] = new boolean[MAX];
	//에라토스테네스의 체 방식으로 미리 소수를 판별해놓기.
	isPrime[0] = isPrime[1] = true; // 소수는 false
	for (int i = 2; i < isPrime.length; i++) {
	if (!isPrime[i]) {
	for (int j = i + i; j < isPrime.length; j += i) {
	isPrime[j] = true;
	}
	}
	}
	//입력된 값을 바탕으로 결과 출력하기
	int n = Integer.parseInt(br.readLine());
	while (n != 0) {
	boolean isGoldbach = false;
	for (int i = 2; i <= n / 2; i++) {
	if (!isPrime[i] && !isPrime[n - i]) {
	System.out.println(n + " = " + i + " + " + (n - i));
	isProve = true;
	break;
	}
	}
	if (!isGoldbach) {
	System.out.println("Goldbach's conjecture is wrong.");
	}
	n = Integer.parseInt(br.readLine());
	}
	br.close();
	}
	}

view raw N6588.java hosted with ❤ by GitHub