[백준 1644] 소수의 연속합 자바 //le_effort//

1806번 문제와 비슷한 문제이다 

https://suhyeokeee.tistory.com/2

백준 1806 부분합 자바 //le_effort//

위 문제와 똑같은 투포인터 알고리즘으로 1806번 문제와는 달리 소수의 연속합을 구하는 것이다

이 문제에선 sum이 목표치와 도달하면 cnt를 증가 시켜주면 된다

 

소수를 구하는 알고리즘은 에라토스테네스의 체를 사용했다

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static boolean prime[];
    static ArrayList<Integer>prime_list = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        prime = new boolean[n+1];
        isPrime();
        for(int i=2; i<=n; i++) {
            if(!prime[i]) {
                prime_list.add(i);
            }
        }    // 소수를 넣어준다
        
        
        int start =0,end=0,sum=0,cnt=0;
        while(true) {
            if(sum==n) {
                cnt++;
                sum-=prime_list.get(start);
                start++;
            }
            else if(sum>n) {
                sum-=prime_list.get(start);
                start++;
            }
            else if(end == prime_list.size()) {
                break;
            }
            else {
                sum+=prime_list.get(end);
                end++;
            }
        }
        System.out.println(cnt);
    }
    public static void isPrime() {
        for(int i=2; i<=n;i++) {
            for(int j=i*2; j<=n; j+=i) {
                prime[j] = true;
            }
        }
    }
}