A small C program to print the biggest prime number

Here it is (447 bytes):

int m=2013265921,N=1,t[1<<27],a,*p,i,e=139390849,s,c,U=1;g(d,h){for(i=s;i<1<<26;
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(){for(*t=2;e/=2;){N*=
2;U=U*1LL*(m+1)/2%m;for(s=N;s/=2;)g(137,0);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;
for(s=1;s<N;s*=2)g(749463956,1);for(a=0,p=t;p<t+N;)a+=*p<<(e&1),*p++=a%10,a/=10;
}while(!*--p);for(--*t;p>=t;)putchar(48+*p--);}

This program computes 2^136279841-1, which is the biggest known prime number in 2024 (about 41 million digits !). For more information about how it was found and who found it, look at the GIMPS Project .

I compiled it successfully with gcc with Linux. In order to compile it, your C compiler must support the 64 bit long long type.

In order to have a small and yet asymptotically efficient code, I decided to do the computation of 2^N-1 directly in base 10. The power involves repeated squarings and multiplications by two. The squarings are implemented by doing fast convolutions using a Number Theoretic Transform.

A previous version of this program to compute 2^6972593-1 won the International Obfuscated C Code Contest of Year 2000.

Thanks to Marco Cecchi and Viktor Korsun who suggested some syntactic changes to save a few characters.

The following slightly longer program accepts any number N as parameter such as 2 <= N <= 445000000 and computes 2^N-1 in base 10:

int m=2013265921,N=1,t[1<<27],a,*p,i,r,s,c,U=1;g(d,h){for(i=s;i<1<<26;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(e,v)char**v;{for(e=atoi(v[1]),
r=0;e>>r+1;r++);for(*t=2,p=t;r--;){if((2*(p-t)+3)>N)N*=2,U=U*1LL*(m+1)/2%m;for(s
=N;s/=2;)g(137,0);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;for(s=1;s<N;s*=2)g(
749463956,1);for(a=0,p=t;p<t+N;)a+=*p<<(e>>r&1),*p++=a%10,a/=10;while(!*--p);}
for(--*t;p>=t;)putchar(48+*p--);}

These programs are Freeware.