ING

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 골드바흐의 추측 ( 문제 번호 : 9020 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

* 2n의 범위까지 나오는 소수들을 미리 구한 뒤 소수의 개수를 더해주는게 시간을 줄일 수 있다.

  반복해서 사용하게 될 경우 그때 그때 다시 계산해줄 필요가 없으므로 자바 또한 이러한 방식으로 바꿔서 풀면

  좋을 것 같다

* 이 문제의 포인트는 두 소수 차이가 적은 값을 구하는 것이다.

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		boolean[] num_list = new boolean[10001];
		for(int i=2; i<=10000; i++){
			int result = 0;
			int half = (int)Math.sqrt(i);
			if(i==1) result++;

			for(int j=2; j<=half; j++){
				if(i%j==0){
					result++;
					num_list[i]=false;
					break;
				}
			}
			
			if(result==0){
				num_list[i]=true;
			}
		}

		int t = scan.nextInt();
		for(int i=0; i<t; i++){
			int n = scan.nextInt();
			int k = n;
			int diff =n;
			for(int j=2; j<=n/2; j++){
				if(num_list[j] && num_list[n-j]){
					if(diff > (n-2*j)){
						k=j;
						diff = n-2*j;
					}
				}
			}

			System.out.println(k+" "+(n-k));
		}
		scan.close();
	}

}

2) PYTHON

import math
k = 10001
num_list = [True]*k
for i in range(1, k):
    if i == 1:
        continue
    for k in range(2, int(math.sqrt(i))+1):
        if i % k == 0:
            num_list[i] = False
            break

t = int(input())
for _ in range(t):
    n = int(input())
    k = n
    diff = n
    for i in range(2, n//2 + 1):
        if num_list[i] and num_list[n-i] and diff > (n-2*i):
            k = i
            diff = n-2*i
    print(k, n-k, end=" ")

여러분도 한번 풀어보세요!