[백준] 1644 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

2021-01-20

---

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main1644 {
    public static int N, arr[];
    public static ArrayList<Integer> list;
    
    public static void solve() {
        arr[0] = 1;
        arr[1] = 1;
        for(int i = 2; i <= N; i++) {
            for(int k = 2; (i * k) <= N; k++) {
                if(arr[i*k] == 0) {
                    arr[i*k] = 1;
                }
            }
        }
        for(int i = 0; i <= N; i++) {
            if(arr[i] == 0) {
                list.add(i);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N+1];
        list = new ArrayList<>();
        solve();
        int start = 0;
        int end = 0;
        int count = 0;
        int sum = 0;
        
        while(start < list.size()) {
            if(sum >= N) {
                sum -= list.get(start++);
            } else if(end == list.size()) break;
            else {
                sum += list.get(end++);
            }
            if(sum == N) {
                count++;
            }
        }
 
        System.out.println(count);
    }
}
 

#문제풀이

 

소수찾기 + 투 포인터 알고리즘 문제이다.

 

1. 에라토스테네스의 체로 소수를 찾고, arr배열에 소수가 아닌 경우를 1로 표시하였다. 

 

2. arraylist에 arr배열에서 소수(값이 0인 경우)를 찾아서 넣었다. 

 

3. 투 포인터 알고리즘으로 연속된 합 중 N과 같은 경우를 찾는다.