BOJ_1644_소수의 연속합_java

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

1644번: 소수의 연속합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 백준 1644번 소수의연속합
 골드 3
 */
public class BOJ_1644_소수의연속합 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        System.out.println(solution(N));

    }

    public static int solution(int N){
        boolean[] primeNum = findPrimeNumbers(N);
        List<Integer> primenumSum = getPrimenumSum(primeNum);

        int cnt = 0;

        int start = 0, end = 0, sum=0;
        while (true){
            if(sum >= N ) sum -= primenumSum.get(start++);
            else if(end == primenumSum.size()) break;
            else sum += primenumSum.get(end++);
            if(N==sum) cnt++;
        }

        return cnt;
    }

    // 시작부터 각 위치까지의 연속합
    public static List<Integer> getPrimenumSum(boolean[] primeNum){
        int size = primeNum.length;
        List<Integer> primeSumList = new ArrayList<>();

        for (int i = 1; i<size; i++){
            if (!primeNum[i]){
                primeSumList.add(i);
            }
        }

        return primeSumList;
    }

    // 에라토스테네스의 체
    public static boolean[] findPrimeNumbers(int N){
        boolean[] primeNum = new boolean[N+1];
        primeNum[0] = primeNum[1] = true;
        for (int i = 2; i<=Math.sqrt(N); i++){
            if (!primeNum[i]){
                for (int j = i*i; j <=N; j+=i){
                    primeNum[j] = true;
                }
            }
        }
        return primeNum;
    }


}