2008/07/15

The smallest C program to print the biggest prime number

这个世界上,令人敬仰的人太多了~~~~ Fabrice Bellard 就是一个这个就是他的小程序,用来计算目前已知的最大质数的程序一共只有475字节,是一个一行程序。
可以通过任何C编译器编译。



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--);}


格式化之后,它看起来这样:


#include <stdio.h>
#include <stdlib.h>

int m=754974721,N,t[1<<24],a,*p,i,e=16804127,j,s,c,U;
f(int d){
for(s=1<<24;s/=2;d=d*1LL*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])*1LL*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--);
}




计算输出的结果有 9M 之巨。
另外说一句,这个哥哥 72年出生,今年36岁。
发表评论