백준 6588

▶ 6588번 문제 - 골드바흐의 추측

 

▶ 풀이방법

- 밑의 코드를 사용할 경우 결과값은 잘 나오지만, 백준 채점단계에서 여러번 반복되는의 소수 판별방식으로 인해 시간초과 오류 발생.

import java.util.*;
public class Main{
	public static void main(String[] args) throws Exception{
		BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		long n;
		while(true) {
			n = Integer.parseInt(br.readLine());
			if(n == 0) break; //0입력되면 stop
			
			long a2 = 1, b2 = 1;
			f: for(int i = 3; i <= n/2; i++) {
				for(int j = 2; j <= Math.sqrt(i); j++) { //i가 소수인지 판별
					if(i % j == 0) continue f;
				}
				
				long b = n-i;
				for(int j = 2; j <= Math.sqrt(b); j++) { // b가 소수인지 판별
					if(b % j == 0) continue f;
				}
				
				if(b - i > b2 - a2) { //두 수의 차가 가장 클 경우 출력.
					b2 = b;
					a2 = i;
					bw.write(String.valueOf(n + " = " + i + " + " + b) + "\n");
				}else if(a2 == 1 && b2 == 1) bw.write("Goldbach's conjecture is wrong.\n");
			}
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}

 

- 위의 시간초과 해결하기 위한 방법. -> 에라토스테네스의 체 사용. (소수 판별 알고리즘)

- 참고글( https://brenden.tistory.com/48 )

 

import java.io.*;
import java.util.Arrays;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		//소수판별(에라토스테네스의 체)
		int max = 1000000;
		Boolean arr[] = new Boolean[max+1];
		Arrays.fill(arr, true);
		for(int i = 2; i <= max; i++) {
			for(int j = i*2; j <= max; j+=i) { //소수가 아닌것은 false처리
				if(!arr[j]) continue;
				arr[j] = false;
			}
		}
		
		while(true) {
			int num = Integer.parseInt(br.readLine());
			if(num == 0) break; // 0입력되었을때 중지.
			
			boolean b = false;
			for(int i = 2; i <= max/2; i++) {
				if(arr[i] && arr[num-i]) {
					bw.write(String.valueOf(num + " = " + i + " + " + (num-i)) + "\n");
					b = true;
					break;
				}
			}
			if(b == false) bw.write("Goldbach's conjecture is wrong.\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}