[Java] 백준17103 골드바흐 파티션: 에라스토테네스의 체

문제

 

 

문제 해결 방법

1. 에라스토테네스의 체 이용하여 소수 구하기
2. 소수의 합 구하기

 

시간 제한이 짧으므로, 시간 복잡도를 고려하여 코드를 구성하는 게 중요하다.

 

 

에라스토테네스의 체

https://skylarcoding.tistory.com/361
 

 

문제 반례 찾는 법

아래 링크에서 확인할 수 있다.

https://skylarcoding.tistory.com/303

 

 

 

 

코드 해설

1. 소수 판별 체를 한번만 만들어 시간 복잡도 개선
2. 소수끼리의 합 구할 때, 이중 for 문이 아닌 n = i + (n - i) 공식 이용하여 시간 복잡도 개선

 

위 두 가지만 유의하고 이전의 에라스토테네스의 체 문제 풀이들을 참고하면 쉽게 풀 수 있다.

 

[Java] 백준1929 소수 구하기 : 에라스토테네스의 체

출처: https://skylarcoding.tistory.com/361 [코딩 공부하는 블로그:티스토리]

 

[Java] 백준4948 베르트랑 공준 : 에라스토테네스의 체

출처: https://skylarcoding.tistory.com/362 [코딩 공부하는 블로그:티스토리]

 

 

 

 

 

코드

package AlgorithmStudy.src.silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class S17103 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long testCase = Integer.parseInt(br.readLine());
        if (1 > testCase || testCase > 100) return;

        // 소수 판별 체 한번만 만들기
        boolean[] list = isPrime();

        // 테스트 케이스 입력
        for (int i = 0; i < testCase; i++) {
            int n = Integer.parseInt(br.readLine());
            if (2 >= n || n > 1000000) return;
            addPrime(n, list);
        }
    }

    // 에라스토테네스의 체
    /*
    1. n 보다 작은 수의 소수 구하기
    2. 소수끼리 합이 n 인 것 구하기
     */
    public static boolean[] isPrime() {
        boolean[] list = new boolean[1000001];

        list[0] = true;
        list[1] = true;

        // 소수 구하기
        for (int i = 2; i * i <= list.length - 1; i++) {
            if (!list[i]) {
                for (int j = i * i; j <= list.length - 1; j += i) {
                    list[j] = true;
                }
            }
        }

        return list;
    }

    public static void addPrime(int n, boolean[] list) {
        int cnt = 0;
        // 소수끼리 합 구하기
        for (int i = 2; i <= n / 2; i++) {
            if (!list[i] && !list[n - i]) {     // n = i + (n - i) 이기 때문에.
                cnt ++;
            }
        }
        System.out.println(cnt);
    }
}