#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TABSIZE 10000000
static int primeS[TABSIZE];
static int 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;
int head, tail, Ans, length, sum, tail_indx, sum_t;
int prime_max;
// stt = time(NULL);
n = maketable(N);
prime_max = primeS[n - 1];
// printf("n = %d(%d)\n", n, p);
for(i = 1, sum = 2; (sum += primeS[i]) <= prime_max; i++)
;
while(foundp(sum -= primeS[i--], n) == 0)
;
Ans = sum, head = 2, tail = primeS[i], tail_indx = i, length = i + 1;
for(i = 1; (sum += (primeS[++tail_indx] - primeS[i - 1])) <= prime_max; i++) {
for(j = 1, sum_t = sum; (sum_t += primeS[tail_indx + j]) <= prime_max; j++)
;
while(j > 1) {
if(foundp(sum_t -= primeS[tail_indx + j--], n)) {
Ans = sum = sum_t, head = primeS[i], tail = primeS[tail_indx += j], length += j;
break;
}
}
}
printf("%d : %d to %d, %d\n", Ans, head, tail, length);
printf("foundp: %d\n", kfp);
// end = time(NULL);
// printf("time: %d sec\n", end - stt);
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 */