[백준 / 골드3] 1644 소수의 연속합 (Java)

에라토스테네스의 체에서 소수인 i로 거를 때 i x j (j < i) 까지는 이미 검증 되었다.
예를 들어 2로 거르면 3 x 2는 이미 걸러졌으므로 3으로 거를 때 3 x 3부터 시작하면 된다.

문제 보기

사용한 것

• 소수를 효율적으로 판별하기 위한 에라토스테네스의 체
• 연속된 구간의 합들을 효율적으로 계산하기 위한 구간합

풀이 방법

• N을 입력 받는다.
• 에라토스테네스의 체를 이용하여 N까지의 모든 소수를 List에 담아 반환한다.
• 반환된 List로 구간합을 arr에 저장한다.
• l = -1, r = 0 부터 시작하여 일정 구간합이 N과 일치하면 answer을 증가시킨다.
• answer을 출력한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Integer> primeNums = getPrimeNums(N);
        int[] arr = new int[primeNums.size()];
        int sum = 0;
        for (int i = 0; i < primeNums.size(); i++) {
            sum += primeNums.get(i);
            arr[i] = sum;
        }

        int l = -1;
        int r = 0;
        int answer = 0;
        while (r < arr.length) {
            int num1 = l == -1 ? 0 : arr[l];
            int num2 = arr[r];
            int diff = num2 - num1;
            if (diff == N) {
                answer++;
                r++;
            } else if (diff < N) {
                r++;
            } else {
                if (l + 1 == r) {
                    r++;
                } else {
                    l++;
                }
            }
        }

        System.out.println(answer);
    }

    static List<Integer> getPrimeNums(int max) {
        if (max <= 1) {
            return Collections.emptyList();
        }

        boolean[] isPrimeNum = new boolean[max + 1];
        for (int i = 2; i <= max; i++) {
            isPrimeNum[i] = true;
        }

        for (int i = 2; i * i <= max; i++) {
            if (isPrimeNum[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrimeNum[j] = false;
                }
            }
        }

        List<Integer> primeNums = new ArrayList<>();
        for (int i = 2; i <= max; i++) {
            if (isPrimeNum[i]) {
                primeNums.add(i);
            }
        }

        return primeNums;
    }
}