The smallest C program to print the biggest prime number

Here it is (475 bytes):

int m=754974721,N,t[1<<24],a,*p,i,e=16804127,j,s,c,U;f(d){for(s=1<<24;s/=2;d=d*1
LL*d%m)if(s<N)for(p=t;p<t+N;p+=s)for(i=s,c=1;i;i--)a=*p+p[s],p[s]=(m+*p-p[s])*1L
L*c%m,*p++=a%m,c=c*1LL*d%m;for(j=0;i<N-1;){for(s=N/2;!((j^=s)&s);s/=2);if(++i<j)
a=t[i],t[i]=t[j],t[j]=a;}}main(){*t=2;U=N=1;while(e/=2){N*=2;U=U*1LL*(m+1)/2%m;f
(362);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;f(415027540);for(a=0,p=t;p<t+N;)a+=*p
<<(e&1),*p++=a%10,a/=10;}while(!*--p);t[0]--;while(p>=t)printf("%d",*p--);}

This program computes 2^32582657-1, which is the biggest known prime number (9.8 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 i86 Linux. It takes about 2 minutes 43 on a 2.4 GHz Pentium 4. In order to compile it, your C compiler must support the 64 bit long long type.

This program basically converts from base 2 to base 10. It is a non trivial task because it deals with numbers of millions of digits. The usual method (with repeated divisions by 10^N) would be far too slow. So I decided to use an Integer Fast Fourier Transform. I believe it is one of the smallest implementation of such an algorithm.

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

This program is Freeware.