エラトステネスのふるいとスライディングウィンドウ
まずエラトステネスのふるいで N 以下の素数をすべて求めます。次に、添字 left から right までの連続する素数の区間と、その合計を管理します。合計が N より小さい間は右端を伸ばします。合計が N 以上になったら、等しい場合は答えに加え、最も左の素数を区間から取り除きます。素数はすべて正なので、区間を伸ばすと合計は増加し、先頭の要素を除くと合計は減少します。そのため、両方のポインタは前にだけ進み、連続する素数の区間をそれぞれ一度ずつ調べれば十分です。
N = 1 の場合、N 以下に素数は存在しないため答えは0です。素数がない入力も空のリストとして処理できるので、同様に0になります。入力の上限は4,000,000なので、各素数と個数は int に収まり、累積和には安全のため long を使います。
ふるいの時間計算量は O(N log log N)、空間計算量は O(N) です。素数の個数を P とすると、ウィンドウ走査は O(P) であり、上限の範囲では O(N) です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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);
}
}