BOJ. Consecutive prime sum (1644)

Problem: BOJ 1644 — Sum of Consecutive Primes

Sieve and sliding window

First generate every prime not greater than N with the Sieve of Eratosthenes. Then keep a window of consecutive primes with indices from left through right and its sum. Extend the right end while the sum is less than N; once it reaches or exceeds N, count it if equal and remove the leftmost prime. Because all primes are positive, extending the window can only increase its sum and removing its first element can only decrease it. Thus each pointer only moves forward, and every consecutive-prime range is considered once.

If N = 1, there are no primes at most N, so the answer is zero; the same empty-prime-list behavior handles any input with no primes. The input bound is at most 4,000,000, so int safely stores each prime and the count, while long safely stores the running sum.

The sieve takes O(N log log N) time and O(N) space. The window scan takes O(P) time for P primes, which is O(N) in the upper bound.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine().trim());

        boolean[] composite = new boolean[n + 1];
        for (int p = 2; p <= n / p; p++) {
            if (!composite[p]) {
                for (int multiple = p * p; multiple <= n; multiple += p) {
                    composite[multiple] = true;
                }
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int value = 2; value <= n; value++) {
            if (!composite[value]) {
                primes.add(value);
            }
        }

        int left = 0;
        long sum = 0;
        int count = 0;
        for (int right = 0; right < primes.size(); right++) {
            sum += primes.get(right);
            while (sum >= n) {
                if (sum == n) {
                    count++;
                }
                sum -= primes.get(left++);
            }
        }

        System.out.println(count);
    }
}