백준 9020번 골드바흐의 추측 / 백준 단계별로 풀어보기 8단계 / 8. 기본 수학 2

백준 8단계 6번 문제 - 9020 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

 

 

 

---

8. 기본 수학 2 (6) 백준 9020번 문제 골드바흐의 추측

---

문제

---

 

 

 

 

---

정답 인정 코드

---

 

import java.util.Scanner;
 
public class Main {
    
    public static boolean prime[] = new boolean[10001];
 
    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; // (n/2) - (n/2) = 0 으로 두 수의 차이가 가장 작다
        
           get_prime();
            while(true) {
                if(prime[a] == false && prime[b] == false) { // n/2값이 소수라면
                    break;                                   // while문 나가고 출력
                }else {            // n/2값이 소수가 아니라면
                    a--;
                    b++;        // n/2값에 1을 더하고 빼서 소수가 나올 때까지 반복한다
                }
            }
            System.out.println(a + " " + b);    //두 수는 공백으로 구분한다
        }
 
    }
    
    public static void get_prime() { //소수인지 판별하는 에라토스테네스의 체. false면 소수
        prime[0] = true;
        prime[1] = true;    //0과 1은 소수가 아니다
        
        for(int i = 2; i < Math.sqrt(prime.length); i++) {    //2부터 배열 끝의 제곱근까지 확인하면 소수
            for(int j = i * i; j < prime.length; j += i) {    //배수들을 지워나간다
                prime[j] = true;
            }
        }
    }
}

 

n / 2에서 1을 더하고 빼는 과정을 생각해내는 것이 핵심이라면 핵심

 

 

 

---

 

끝나지 않는 에라토스테네스...

그래도 8단계도 끝!