[BOJ_6588/JAVA] 골드바흐의 추측

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

문제

풀이

에라토스테세스의 체 알고리즘에 관한 문제이다.

에타토스테네스,, 골드바흐 ,,, 그만 좀 나대고 그냥 발씻고 잘것이지,,, 

 

암튼 Silver1의 문제인데다 정답률이 25%여서 못풀것이라 생각하고 기대도 안했다.

하지만!! 바로 성공 ㅠㅠ 진짜 아직 갈길이 멀지만 그래도 점점 실력이 늘어가는 것을 확인 ㅠ...ㅠ엉엉

 

풀이 방법은

1. 1000000까지의 소수를 전부 판별하였다.

2. 3부터 차례로 소수로 빼주었다. 그러면, 8-3=5 가 되고, 5는 소수이기때문에 3+5가 정답이다.

42의 경우에는 42-3=39는 소수가 아니므로 3 다음 소수인 5를 빼주면 42-5=37이고 37은 소수이므로 5+37이 정답.

3. 만약 for를 다 돈 후에도 소수가 아니면 "Goldbach's~~~" 출력해주었다.

 

코드

package Week05;

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

public class BOJ6588 {
	
	static boolean [] flag = new boolean[1000000+1];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		boolean isTrue;

		param();		// 소수 판별
		
		while(true) {
			String input = br.readLine();
			int num  = Integer.parseInt(input);
			
			if(num==0) {
				break;
			}
			
			int a=0;
			int b=0;
			isTrue=false;
			
			for (int i=3;i<flag.length;i++) {
				
				if(!flag[i]) {
					int minus = num-i;
					if(!flag[minus]) {
						a=i;
						b=minus;
						sb.append(num+" = "+a+" + "+b+"\n");
						isTrue=true;
						break;
					}
				}
			}
			if(!isTrue) {
				sb.append("Goldbach's conjecture is wrong."+"\n");
			}
			
		}
		System.out.println(sb);
	}
	
	static void param() {
		
		flag[0]=flag[1]=true;
		
		for(int i=2;i<Math.sqrt(flag.length);i++) {
			if(flag[i]) {
				continue;
			}
			for(int j=i*i;j<flag.length;j+=i) {
				flag[j]=true;
			}
		}
	}

}

 

감격스러운 나의 코드를 보시오 ㅠㅠ 아직 허접할 수도 있겠지만 알고리즘 쩔쩔쟁이는 나에게 큰 행복...