#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TABSIZE 1000000
static int primeS[TABSIZE];
static int ks, kfp;
int maketable(int N) {
int n, i, r, q, idx;
div_t qr;
primeS[0] = 2;
primeS[1] = 3;
idx = 2;
for (n = 4; n < N; n++) {
i = 0;
do {
qr = div(n, primeS[i]);
if (qr.rem == 0)
break;
i++;
} while (primeS[i] < qr.quot);
if (qr.rem > 0) {
primeS[idx] = n;
idx++;
if (idx > TABSIZE) {
fprintf(stderr, "table size is too small, aborted. idx = %d\n", idx);
exit(-1);
}
}
}
return idx;
}
int foundp(int s, int n) {
int max, min, mid;
kfp++;
max = n - 1; min = 0;
while (max >= min) {
mid = (max + min) / 2;
if (primeS[mid] == s)
return 1;
if (primeS[mid] < s)
min = mid + 1;
else
max = mid - 1;
}
return 0;
}
int task(int N) {
int n, s, p;
int i, j, k;
int max_i, max_j, max_k, max_s;
time_t stt, end;
stt = time(NULL);
n = maketable(N);
p = primeS[n - 1];
printf("n = %d(%d)\n", n, p);
max_i = max_j = max_k = max_s = 0;
for (i = 0; i < n; i++) {
s = 0;
for (k = 1, j = i; j >= 0; --j, k++) {
s += primeS[j]; ks++;
if (s > p)
break;
if ((k > max_k) && (s % 2) && foundp(s, n)) {
if (k > max_k) {
max_i = i; max_j = j; max_k = k; max_s = s;
}
}
}
}
printf("max prime: %d, series: form %d to %d (%d)\n", max_s, primeS[max_j], primeS[max_i], max_k);
end = time(NULL);
printf("time: %d sec\n", end - stt);
printf("sum: %d, foundp: %d\n", ks, kfp);
return 0;
}
#define D 1000000
int main(int argc, char *argv[]) {
// if (argc == 2)
// task(atoi(argv[1]));
// else
// for (;;) {
task(D);
// fflush(stdout);
// }
// return 0;
}
/* end */