백준 9020번 : 골드바흐의 추측[Java]

문제 출처

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

import java.util.Scanner;
public class d021_Q9020 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int i = 0; i < T; i++) {
			int n = sc.nextInt();
			int a = n / 2;
			int b = n / 2;
			
			while(true) {
				if(check_prime(a) && check_prime(n - a)) {
					System.out.println(a + " " + b);
					break;
				}
				else {
					a--;
					b++;
				}
			}
		}
		sc.close();
	}
	
	public static boolean check_prime(int n) {
		int i = 2;
		while(i <= Math.sqrt(n)) {
			if(n % i++ == 0) {return false;}
		}
		return true;
	}

}

 

일단 문제 조건이 두 숫자의 차이가 가장 적게 해야한다는걸 생각해서

각각의 숫자를 a와 b로 놓고 숫자의 절반부터 시작했다.

a는 점점 줄여가고 b는 점점 늘려가다보면

a와 b가 모두 소수인 부분이 나올 것이고 그럼 그게 정답!

 

while문이 상당히 많은 코드라 시간초과가 나올까봐 두근두근 했는데 문제 조건 10000보다 작은 수가 입력된다는 걸 보고 9998까지 입력했을때 2를 넘지 않길래 제출했고 맞았다.