「PE#50」Consecutive prime sum - 双指针

PE 氵题 Link: Problem 50 - Project Euler

简要题意

求一个小于 10^6 的能表示为最多连续质数的和的质数

比如 41 = 2 + 3 + 5 + 7 + 11 + 13 10^2 以内能表示为最多连续质数和的质数

Consecutive prime sum

The prime 41 , can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953 .

Which prime, below one-million, can be written as the sum of the most consecutive primes?


题解

由于素数是单调的, 所以考虑双指针即可

下面这个程序本地跑了10s就过了(((

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
#include <bits/stdc++.h>

#define int long long

const int N = 1000000;

int cnt;
int pri[N];
bool vis[N + 10];

void pre () {
for (int i = 2; i <= N; i++) {
if (!vis[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= N; j++) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}

signed main () {
pre();
int sum, fl;
int ansl = 1, ansr = 0, ans = pri[1];
for (int i = 1; i <= cnt; i++) {
int left = 1, right = 0;
int _l = 1, _r = 0;
sum = 0;
while (left <= i) {
while (right < cnt && sum < pri[i]) sum += pri[++right];
if (sum == pri[i] && right - left > _r - _l) _r = right, _l = left;
sum -= pri[left++];
}
if (_r - _l >= ansr - ansl) {
ansr = _r, ansl = _l;
ans = pri[i];
}
}
printf("[%lld, %lld] => %lld\n", ansl, ansr, ans);
}
坚持原创技术分享,您的支持将鼓励我继续创作!