백준 [java 자바] 6588번 : 골드바흐의 추측

언뜻 보기에는 쉬운 문제 같지만 사실 시간 때문에 고민을 좀 해야 하는 문제이다.

짝수인 수를 소수인 두 수의 합으로 나타내라는 문제이다.

import java.util.*;
import java.io.*;


class Main{
	static int check(int i) {
		int j;
		int ok = 0;
		for(j = 3;j*j<=i;j++) {
			
			if(i%j == 0) {
				ok = 1;
				break;
			}
		}
		return ok;
	}

 public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    while(true) {
    	int n = Integer.parseInt(br.readLine());
    	if(n == 0) break;
    	
    	
    	int i;
    	int j;
    	int k = 1;
    	int ok = 0;
    	int nn = 0;
    	for(i = 3;i<n;i+=2) {
    		
    			if(check(i) == 0) {
    				ok = 1;
    				if(check(n-i) == 0) break;
    			}
    		
    		
    	}
    	if(ok == 1) {
    		
			sb.append(n).append(" = ").append(i).append(" + ").append(n-i).append("\n");
    	}
    	
    	else sb.append("Goldbach's conjecture is wrong.\n");
    	
    	}
    	System.out.println(sb);
    	
    }
 }

우선 3부터 2씩 늘려가면서 소수인지 판단하고 n에서 그 수를 뺀 수도 소수인지 판단하게 하였다. 그리고 StringBuilder을 통해 출력 시간을 줄여주었다. 

 나는 옛날에 책으로 공부할 때 소수를 판단하는 함수를 for문을 해당 수의 루트만큼만 돌리면 된다는 걸 배운 적이 있지만 이걸 몰랐던 사람들은 많이 어려웠을 수도 있을 것 같다.

 

알아야 할 점: 

1. StringBuilder을 할 때 변수와 문자를 함께 써야할 경우 append를 사용하여 연결해준다.

2. 소수인지 모두 다 판단할필요가 없으니 그때그때 판단하기 위해 함수를 사용한다.

 

다른 사람의 코드와 다른 점 : 없다