Skip to content

Instantly share code, notes, and snippets.

@waleedsamy
Created December 14, 2015 14:26
Show Gist options
  • Save waleedsamy/0bbaacc929c52cda6176 to your computer and use it in GitHub Desktop.
Save waleedsamy/0bbaacc929c52cda6176 to your computer and use it in GitHub Desktop.
A small C program to print the biggest prime number
/* source: http://bellard.org/mersenne.html */
int m=1711276033,N=1,t[1<<25]={2},a,*p,i,e=39717691,s,c,U=1;g(d,h){for(i=s;i<1<<
24;i*=2)d=d*1LL*d%m;for(p=t;p<t+N;p+=s)for(i=s,c=1;i;i--)a=p[s]*(h?c:1LL)%m,p[s]
=(m*1U+*p-a)*(h?1LL:c)%m,*p=(a*1U+*p)%m,p++,c=c*1LL*d%m;}main(){while(e/=2){N*=2
;U=U*1LL*(m+1)/2%m;for(s=N;s/=2;)g(40,0);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;
for(s=1;s<N;s*=2)g(983983719,1);for(a=0,p=t;p<t+N;)a+=*p<<(e&1),*p++=a%10,a/=10;
}while(!*--p);for(t[0]--;p>=t;)putchar(48+*p--);}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment