공부 115일차: 백준 17103번 골드바흐 파티션 자바 java

17103 골드바흐 파티션

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

17103번: 골드바흐 파티션

 

 

 

---

백준 17103번 문제 골드바흐 파티션

---

문제

---

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/175

공부 96일차: 백준 6588번 골드바흐의 추측 자바 java

골드바흐 관련한 문제는 이번이 3번째다

 

필요한 과정은

1. 소수 구하기

2. 2부터 n/2까지 반복문 돌려서 소수끼리 더해지는지 찾기

(소수를 구할 때 대칭성 때문에 n/2까지만 구해도 되며, 이때문에 문제에서는 '두 소수의 순서만 다른 것은 같은 파티션'이라고 명시되어 있다)

 

 

소수를 구할 때 가장 잘 알려진 알고리즘은 에라토스테네스의 체이다

유튜브에 치면 그 원리가 자세히 나와있다

간단하게 보자면, 위의 표에서 소수인 2, 3, 5, 7, 11... 들의 배수를 하나하나 지우면서 소수가 아닌 수를 거르는 과정이다

1000000까지 어떤 수가 소수인지 확인하는 코드는 다음과 같다

    public static boolean prime[] = new boolean[1_000_001];
    
    //에라토스테네스의 체: false->소수
    public static void get_prime() {
        prime[0] = true;
        prime[1] = true;
        
        for(int i = 2; i < Math.sqrt(prime.length); i++) {    //2부터 구하려는 숫자 범위의 제곱근까지 구한다
            for(int j = i*i; j < prime.length; j += i) { // i의 제곱이라면 -> i*(i보다 작은 수)는 앞선 반복문에서 모두 사라졌을 것이므로 -> 소수가 아니다 
                prime[j] = true;
            }
        }
    }

첫 번째 반복문에서 제곱근까지만 구하는 경우는 쉽게 생각해볼 수 있다

그림처럼, 소수가 아닌 수의 약수들은 대칭성을 가진다

따라서 2부터 구하려는 수의 제곱근까지 구해봤을 때 약수가 없다면 이 숫자는 소수라고 판별할 수 있는 것이다

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    
    public static boolean prime[] = new boolean[1_000_001];
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < t; i++) {
            int count = 0;
            int n = Integer.parseInt(br.readLine());
            get_prime();    //에라토스테네스의 체 이용
            // 소수는 2부터 시작 / 문제에 두 소수의 순서만 다른 것은 같은 파티션 -> n/2까지만
            for(int j = 2; j <= n/2; j++) {    
                if(!prime[j] && !prime[n-j]) {    // j+(n-j)=n. 둘 다 소수라면
                    count++;    // 개수+1
                }
            }
            bw.write(count+"\n");
        }
        bw.flush();
        bw.close();
        
 
    }
    
    //에라토스테네스의 체: false->소수
    public static void get_prime() {
        prime[0] = true;
        prime[1] = true;
        
        for(int i = 2; i < Math.sqrt(prime.length); i++) {
            for(int j = i*i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
 
}
 

 

과정에서 한 설명에 더해 주석에도 자세히 쓰려고 해봤다

 

 

 

 

---