[JAVA] 백준 9020번 골드바흐의 추측 : 소수의 합

9020번: 골드바흐의 추측

 

1. 문제 추상화

 

짝수는 두 소수의 합으로 표현 가능하다. 이 때, 두 소수의 차이가 최소인 경우를 출력하시오.

 

2. 알고리즘 

 

첫 번째 방법

 

조건 : 짝수 - 작은 소수 = 큰 소수

 

해당 조건을 만족하는 작은 소수를 구한다.

작은 소수 중 가장 큰 소수일 때, 두 소수의 차이가 작다.

 

두 번째 방법

 

C는 짝수

C/2 +C/2 = C 

C/2-1 + C/2+1 = C

C/2-2 + C/2+2 = C

.

.

 

반복문을 통해, 하나는 -1 씩, 하나는 + 1씩 해주어서 두 수 모두 소수인 경우를 찾는다.

 

3. 코드

 

첫 번째 방법

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
    
		 // 아리스토테네스의 체 생성
		boolean[] prime = new boolean[10001];
		initializePrimeArray(prime);
		
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int testcase = sc.nextInt();
		
		for(int i = 0; i< testcase; i++) {
			
			int evenNumber = sc.nextInt();
			String result = "";
			
			for( int j = 2; j <= evenNumber - j; j++) {
				if(prime[j])continue;
				if(!prime[evenNumber - j]) { // ( 짝수 - 소수 = 소수) 인지 판별
					result = j + " " + (evenNumber - j);
				}
			}
			
			sb.append(result).append("\n");
		}
		
		System.out.println(sb);
	}
	 // 아리스토테네스 체 초기화
	public static void initializePrimeArray(boolean[] prime) {
		
		prime[0] = true;
		prime[1] = true;
		
		for(int i=2; i*i<prime.length; i++) {
			if(prime[i])continue;
			for(int j=i*i; j<prime.length;j+=i) {
				prime[j] = true;
			}
		}
	}

}

 

 

두 번째 방법

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
        //아리스토테네스의 체 생성
        boolean[] prime = new boolean[10001];
		initializePrimeArray(prime);
        
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
        
		int testcase = sc.nextInt();
		
		for(int i = 0; i< testcase; i++) {
			int evenNumber = sc.nextInt();
            
			int small = evenNumber / 2;
			int big = evenNumber / 2;
			
			String result = "";
			
			while(true) { //반드시 합이 하나는 나오니깐 무한루프 돌려도 된다.
				if(prime[small]== false && prime[big] == false) {  // 두 수 모두 소수인지 판별
					result = small + " " + big;
					break;
				}
                
				small--;
				big++;
			}
			sb.append(result).append("\n");
		}
		
		System.out.println(sb);
	}
	// 아리스토테네스의 체 초기화
	public static void initializePrimeArray(boolean[] prime) {
			
			prime[0] = true;
			prime[1] = true;
			
			for(int i=2; i*i<prime.length; i++) {
				if(prime[i])continue;
				for(int j=i*i; j<prime.length;j+=i) {
					prime[j] = true;
				}
			}
	}

}