[백준] 6588 : 골드바흐의 추측 JAVA 풀이

 

 

에라토스테네스의 체로 소수를 판별하고 그 소수들을 ArrayList에 추가한다.

리스트를 앞과 뒤에서부터 읽어 a+b가 n이 되면 출력을 한 뒤 반복문을 종료한다.

이런 식으로 코드를 작성해볼까 했는데 너무 비효율적인 것 같아 방향을 틀었다.

 

초기에 구상한 코드

import java.io.*;
import java.util.*;
public class Main {
	static boolean[] prime = new boolean[1000001];
	static ArrayList<Integer> list = new ArrayList<Integer>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		get_prime();
		
		while(true) {
			int n = Integer.parseInt(br.readLine());
			if(n==0) break;
			
			loop: for(int i=0;i<list.size();i++) {
				for(int j=list.size()-1;j>=0;j--) {
					if(list.get(i)+list.get(j)==n) {
						System.out.printf("%d = %d + %d\n", n, list.get(i), list.get(j));
						break loop;
					}
				}
			}
		}

	}
	
	static void get_prime() {
		prime[0] = prime[1] = true;
		
		for(int i=2;i<=Math.sqrt(prime.length);i++) {
			if(prime[i]) continue;
			
			for(int j=i*i;j<prime.length;j+=i) {
				prime[j] = true;
			}
		}
		for(int i=0;i<prime.length;i++) {
			if(!prime[i]) list.add(i);
		}
	}

}

이제보니 태클 걸 곳이 한두 군데가 아닌 것 같다 ㅋㅋㅋ

 

 

 

 

 

 

에라토스테네스의 체로 소수를 판별하는 건 그대로 두고,

b - a가 최대인 a + b를 구하는 부분을 메서드로 분리했다.

 

import java.io.*;
import java.util.*;
public class Main {
	// 에라토스테네스의 체로 소수를 판별하기 위한 배열 기본값 false 
	static boolean[] prime = new boolean[1000001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
        // 에라토스테네스의 체로 소수 판별
		get_prime();
		
		while(true) {
        	// 테스트케이스를 입력받음
			int n = Integer.parseInt(br.readLine());
            // 0이 입력됐다면 반복문 종료
			if(n==0) break;
			
            // 메서드의 실행으로 반환된 a값 저장
			int a = make_n(n);
            
            // 두 개의 소수의 합으로 n을 나타낼 수 없다면
			if(a==-1) {
				sb.append("Goldbach's conjecture is wrong.\n");
			}
            // 나타낼 수 있다면
			else {
				sb.append(n+" = "+a+" + ").append(n-a).append('\n');
			}
		}
        // 스트링빌더에 저장된 내용 출력
		System.out.print(sb);

	}
	
    // b - a가 최대가 되는 a + b를 구하는 메서드
	static int make_n(int n) {
    	// a가 최소일 때 b - a가 되므로 그때의 a를 리턴
		for(int i=3;i<=n/2;i++) {
			int a = i;
			int b = n-a;
			if(prime[a]==false&&prime[b]==false) return a;
		}
		return -1;
	}
	
    // 에라토스테네스의 체
	static void get_prime() {
		prime[0] = prime[1] = true;
		
		for(int i=2;i<=Math.sqrt(prime.length);i++) {
        	// 이미 소수가 아니라고 판단한 수라면 넘어감
			if(prime[i]) continue;
			
            // 어떤 수의 배수(=소수가 아닌 수)라면 true로 변경
			for(int j=i*i;j<prime.length;j+=i) {
				prime[j] = true;
			}
		}
	}

}

 

원래는 매번 System.out.printf()을 호출하도록 작성했더니 시간초과가 나왔고

StringBuilder를 사용하는 걸로 해결했다.

 

에라토스테네스의 체를 제대로 이해하고 활용했다는 생각에 성취감을 느낄 수 있었던 문제였다!