资讯频道 → 编程语言
阅读更多

26顶
0踩

编程语言

原创新闻 简单的 C程序输出最大的素数

2010-01-07 14:48 by 副主编 just_cool 评论(10) 有10854人浏览
C++ C C#

声明：ITeye资讯文章的版权属于ITeye网站所有，严禁任何网站转载本文，否则必将追究法律责任！

 C程序(438 bytes)如下:  

int m=167772161,N=1,t[1<<25]={2},a,*p,i,e=34893349,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+*p-a)*(h?1LL:c)%m,
		a+=*p,
		*p++=a%m,
	                c=c*1LL*d%m;
}

main() 
{    
   while(e/=2)
   {  
               N*=2;
               U=U*1LL*(m+1)/2%m;
	for(s=N;s/=2;)g(17,0);
	for(p=t;p<t+N;p++)   
	    *p=*p*1LL**p%m*U%m;
	for(s=1;s<N;s*=2)   
	    g(29606852,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--);
}

 

 

 这个程序用于计算243112609-1，这是已知的最大素数（约1300万位！）。

 

在使用gcc（GNU Compiler Collection，GNU编译器套装）和i386 Linux上能成功的运行，C编译器必须支持64 bit long long 类型，在2.33 GHz Core2 CPU上运行时间不到2 分钟。

 

这个程序之前的版本，用于计算26972593-1，赢得了2000年度International Obfuscated C Code Contest大奖赛的冠军。

 

点击查看更多详情：http://bellard.org/mersenne.html

来自: bellard.org
26
顶
0
踩
评论 共 10 条 请登录后发表评论
10 楼 nwwhbp 2010-07-16 10:19
不魁是高手，代码都写的这么随性 ~！
9 楼 495127903 2010-01-09 14:15
不知道的cpu会不会直接搞挂去..
哈哈
8 楼 fireflyc 2010-01-09 01:36
是够乱的。
weiqingfei 写道
好歹排下版嘛，这么乱。

如果能排版就不会赢得IOCCC大赛了。不过看来时代在“进步”；2000年的冠军居然比以前整齐多了。
7 楼 lwp2000 2010-01-08 18:31 
int m=167772161,N=1,t[1<<25]={2},a,*p,i,e=34893349,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+*p-a)*(h?1LL:c)%m,
		a+=*p,
		*p++=a%m,
	                c=c*1LL*d%m;
}

main() 
{    
   while(e/=2)
   {  
               N*=2;
               U=U*1LL*(m+1)/2%m;
	for(s=N;s/=2;)g(17,0);
	for(p=t;p<t+N;p++)   
	    *p=*p*1LL**p%m*U%m;
	for(s=1;s<N;s*=2)   
	    g(29606852,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--);
}
6 楼 lwp2000 2010-01-08 18:29 
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+*p-a)*(h?1LL:c)%m,   
        a+=*p,   
        *p++=a%m,   
                    c=c*1LL*d%m;   
}
5 楼 Jekey 2010-01-08 10:39
强悍
4 楼 shinezhou 2010-01-08 10:06
牛b


3 楼 鸟哥哥 2010-01-08 09:52
强
可以为我所用了。
2 楼 wolfplanet 2010-01-07 16:02
weiqingfei 写道
好歹排下版嘛，这么乱。

这个程序之前的版本，用于计算26972593-1，赢得了2000年度International Obfuscated C Code Contest大奖赛的冠军。
1 楼 weiqingfei 2010-01-07 15:47
好歹排下版嘛，这么乱。

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • SVN版本控制使用心得

    NULL 博文链接：https://wikimo.iteye.com/blog/352887

  • 版本控制心得

    没有使用版本控制的黑暗时代——版本控制心得（一）     在没有使用版本控制的开发团体中，我所熟悉的一种常用开发方式是：多个开发人员共同负责一个软件的开发，每个人在各自的机器上有整个软件的拷贝，并对之实施编码，分别完成各自任务之后，再通过文本比对工具将各自机器上的不同版本的软件整合到一台机器上。  　　本文就这样的开发方式，提出在软件开发中出现的几个和版本控制密切相关的典型问题

  • 版本控制系统的一些使用心得

    主要介绍svn和git这两个当前主流的版本控制系统，这也是大家使用的比较广泛的。

  • 版本控制实践和学习心得

    1.已SVN和Git为例，心得如下：

  • 版本控制系统的总结

    概述 版本控制系统：是指对各种代码、配置文件及说明文档等文件变更的管理工具。包括：检入和检出控制、分支和合并、历史纪录等。 在我们日常工作中，经常会用到版本控制系统，尤其是在多人协作的项目中。下面就对我使用过的版本控制系统进行的总结。 1、TFS TFS是Team Foundation Server(TFS)的简称，是软件项目生命周期管理工具，版本控制只是它的一小部分功能。另外还包括其他功能，如需...

  • 手把手教你用C语言实现求质数（素数），5大方法任君挑选

    //求1--1000内的质数（素数） #include &lt;stdio.h&gt; int main() { int x = 0; int i = 0; unsigned int count = 0; for (x = 2; x &lt; 1000; x++) //在2到1000之间找质数 { for (i = 2; i &lt; x; i++)...

  • 判断素数的c语言程序_C素数程序

    判断素数的c语言程序Here you will get program for prime number in C. 在这里，您将获得C中素数的程序。 A number that is only divisible by 1 or itself is called prime number. 仅可被1整除的数字或本身...

  • [C语言]输出100以内的所有素数(质数)

    C语言如何打印输出100以内的素数，这里提供代码，思路，帮助理解，并且有详细的代码注释解析

  • 【C语言】输出100内素数

    (1)输出100内的素数(易理解) (2)使用sqrt平方根函数输出 1.概念理解 素数:又称质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 因数:指整数a除以整数b(b≠0) 的商正好是整数而...

  • 【C语言程序02】请用C语言程序输出前50个素数

    请用C语言设计程序输出前50个素数

  • 版本控制——总结

    1.定义 版本控制(Revision control)是一种软体工程技巧，籍以在开发的过程中，确保由不同人所编辑的同一档案都得到更新。 2.原理 版本控制透过文档控制（documentation control）记录程序各个模组的改动，并为每次改动编上序号。这种方法是工程图（engineering drawings）维护（maintenance）的标准做法， 它伴随着工程图从...

  • 版本控制学习心得

    CVS及SVN都是集中式的版本控制系统，而Git是分布式版本控制系统，集中式和分布式版本控制系统有什么区别呢？ 先说集中式版本控制系统，版本库是集中存放在中央服务器的，要先从中央服务器取得最新的版本，然后再把自己的代码推送给中央服务器。 集中式版本控制系统最大的缺点在于必须与中心服务器联网才能工作。 其次，集中式的版本控制是通过比较文件变化，如果把本地的文件全部删除再重新从服务器上获取的话，...

  • 版本管理工作总结

    一、版本规划 版本主要分为常规版本和紧急版本两个部分。 1.常规版本 根据版本迭代周期，结合管理办法进行常规版本规划，包括版本上线、支撑方案评审、版本定版、截止排版的时间规划。 （1）年初输出一版规划时间，邮件公示征询意见； （2）各方无意见则根据规划时间在管理平台创建对应版本。（至少提前2个月） 2.紧急版本 当有重点需求需要紧急上线，或生产故障急需上线修复的情况，需要安排紧急版本上线。 注：紧急版本不走排版定版、支撑方案评审等常规流程，根据实际要求创建版本后安排上线即可。 二、排版定版 根据前面版本规划

  • Git版本控制心得

    Git提交代码注意事项 一般情况，尤其是只维护一个分支的情况，最好不要在GitHub网页界面上进行commit，所有操作在线下做好，保证本地比线上提前，然后正常提交。 常规提交 本地比线上提前 git add --all git commit -m "Some Comment" git push 线上版本高 ...

  • C语言 | 六种方法输出100以内的素数

    一、简单遍历 二、遍历至该数的平方根 三、用x/i来代替sqrt(x) 四、朴素筛法 五、埃式筛法 六、欧拉筛法

  • C语言之输出孪生素数

    孪生素数是指间隔为 2 的相邻素数，例如最小的孪生素数对是3和5，5和7也是(5虽重复但算作2组)。

  • C:素数(质数)的判断以及输出

    C语言中素数(质数)的判断以及输出（附例题）

  • C语言输出某个范围的素数（质数）

    2022年4月20日

  • c语言输出100以内的素数存放数组中,c语言素数(c语言输出100以内素数)

    楼上的还可以具体一些，其实非常简单，如果一个数是素数，只要判断他是否能被2到这个数的开方之间的数整除就行了。int flag=0; if(m==2){ //先判断是不是2 flag=1; } else.#include int main(){ int a=0; int num=0;...

Global site tag (gtag.js) - Google Analytics