[백준 1644] 소수의연속합 <Java>

백준 2003 수들의 합2 응용문제

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class 소수의연속합 {
	static int n;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		ArrayList<Integer> arr = new ArrayList<>();
		int cnt = 0;
		int count = 0;

		boolean arrcheck[] = new boolean[n + 1];

		arrcheck[0] = arrcheck[1] = true;
		for (int i = 2; i * i <= n; i++) {
			if (!arrcheck[i]) {
				for (int j = i * i; j <= n; j += i) {
					arrcheck[j] = true;
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			if (!arrcheck[i]) {
				arr.add(i);
			}
		}

		int sum = 0;
		int left = 0, right = 0;
		while (true) {
			if (sum >= n) {
				sum -= arr.get(left++);

			} else if (right == arr.size()) {
				break;
			} else {
				sum += arr.get(right++);
			}

			if (sum == n) {
				cnt++;
			}

		}

		System.out.println(cnt);

	}

}