1644.少数連続和

1.トラブルシューティング

1-1. エラトステネスのふるい

1-2. ダブルポインタ

2.ソースコード

//소수의 연속합

import java.util.*;
import java.io.*;

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());

		// 에라토스테네스 체
		boolean[] prime = new boolean[n + 1];
		List<Integer> prime_list = new ArrayList<>();
		for (int i = 2; i <= n; i++) {
			if (!prime[i]) {
				prime_list.add(i);
				for (int j = i; j <= n; j += i) {
						prime[j] = true;
				}
			}
		}

		Collections.sort(prime_list);
		twoPoint(n, prime_list);
	}

	private static void twoPoint(int n, List<Integer> prime_list) {
		int left_idx = -1, right_idx = -1;
		int sum = 0, ans = 0;
		while (left_idx < prime_list.size()) {
			while (++right_idx < prime_list.size()) {
				sum += prime_list.get(right_idx);

				if (sum <= n) { // 합이 n과 동일하거나 작은 경우
					if (sum == n)
						ans++;
				} else // 합 > n
					break;
			}

			while (++left_idx < prime_list.size()) {
				sum -= prime_list.get(left_idx);
				if (sum <= n) {
					if (sum == n)
						ans++;
					break;
				}
			}
		}

		System.out.println(ans);
	}
}