C代码求迄今已知最大的素数

Fabrice Bellard仅仅只用447B代码， 计算出已知最大的素数， 大约有1700万位。

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

编译器要求支持64B的long long 类型，Linux 下gcc编译成功，2.3Ghz 双核CPU大约需要2分钟的运行时间。

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

c/cpp Comments(0) Sep 14, 2013 10:30:19 PM