9020_골드바흐의 추측 (JAVA)

9020번: 골드바흐의 추측

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int i=0; i<T; i++){
			int num = sc.nextInt();
			partition(num);
		}
	}
	public static void partition(int num){
		//temp[]!=0이면 소수 (에라토스테네스의체)
        int[] temp = new int[num+1];
		for(int i=2; i<=num; i++){
			temp[i] = i;
		}
		for(int i=2; i<=num; i++){
			for(int j=i+i; j<=num; j+=i){
				temp[j] = 0;
			}
		}

		//x--,y++ 하면서 x+y=num인 x,y 찾기
		int x = num/2; int y = num/2;
		int min = num;
		int ans1=0, ans2=0;
		while(x>=2){
			if(temp[x]!=0 && temp[y]!=0){
				System.out.println(x+" "+y);
				break;
			}
			x--; y++;
		}
	}
}

 

 

 

만약 num/2이 소수라면 바로 출력하고 끝!

왜냐면 num/2 + num/2 = num이고, num/2 - num/2 = 0이므로 차가 가장 적은경우이다. 

 

만약 num/2이 소수가 아니라면 - 차가 가장 작은 경우를 찾아야 한다.

 

예를 들면,

num = 16 일때x=8, y=8 으로 x,y에 각각 num/2 값을 저장해놓고,

(8,8) (7,9) (6,10), (5,11), (4,12), (3,13), (2,14) 이런식으로 == x--, y++ 해주면서

x+y=16이 되면서 x,y가 모두 소수일 때를 찾는다.

 

위의 순서가 진행될수록 == x값이 작아지고 y값이 커질수록

- 두 값의 차는 커지기때문에!x,y가 모두 소수인 조건을 만족한다면 정답이다.

 

 

코드 수행 순서는 다음과 같다.

 

1. 숫자 num을 입력받는다.2. temp[num+1] 을 생성한 다음, num보다 작은 소수를 모두 찾는다.

   ( 'temp[i]!=0 이면 소수' 로 구현했다 )

 

2. x=num/2, y=num/2로 초기화하고

   x--,y++하면서 temp[x]!=0, temp[y]!=0인 조건을 만족하는 x,y를 찾는다.