C程序求素数详解

《C程序求素数详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ByjuzhongEmail：ziou2004@163.com2015年1月25日C程序求素数详解用C语言编程求解1亿以内所有素数的原理与实现1.原理与证明我们知道，大于1的自然数，可以划分为素数p和非素数!p。假若给出一个大于1的自然数，如果它不是“非素数”，那么可以肯定它是“素数”，非此即彼嘛！为了记叙方便，以下所述，遇到“自然数”或“整数”，均指大于1的整数。素数也叫质数，但在将一个整数分解为质因子乘积时，通常称为质数，所以以下所述，有时叫素数，有时叫质数，都是同一种东西，只不过在不同环境下，称谓不同。我们又知道：一个非素数可以分解为至少两个质

2、数的乘积。而素数不能。!P=p1*p2*…P!=p1*p2既然，一个非素数N能分解为至少两个质数的乘积，那么每个质因数一定比这个非素数小（显而易见！）。(p1

3、性3:一定存在小于或等于这个非素数平方根的素数p，可以整除这个非素数。因为非素数能分解为至少两个质数的乘积，其中的必有一个质数一定不大于√!P，这个是显而易见的。!P=p1*p2*…(p1<=√!P

4、

5、p2<=√!P

6、

7、…)=1由上面所述，我们可以根据是否具备上述属性之一，来判断一个整数是否为素数。C语言编程，枚举1亿范围内的所有整数，逐个判断是否为素数。2.C语言实现a.较慢的方法：根据属性2，判断一个整数是否为素数，我们可以将这个整数，对比他小的所有整数求余，如果发现有结果为0的，可以判断它为非素数。如果都没发现结果为0，可以断定它是素数。#in

8、clude#include#includeintmain(void){intlimit=0;start:printf("请输入上限数（输入0退出）：");scanf("%d",&limit);if(limit<0

9、

10、limit>100000000){printf("请输入大于1且不大于100000000的自然数");gotostart;}if(limit==0)return0;intmaxp=0;//用来保存最大的素数intcount=1;//用来保存素数个数//freopen("out.txt"

11、,"w+",stdout);//如果结果需输出到文件，请去掉注释printf("2t");clock_tstart,end;//用来计算程序耗时的start=clock();for(inti=2;i<=limit;i++){for(intt=2;t

12、是：%d,最大的素数是%d",limit,(double)(end-start)/CLOCKS_PER_SEC,count,maxp);gotostart;}!2b.较快的方法：根据属性3，利用开方将要测试的求余的最多个数大幅减少，例如要测试1亿是否是素数，则最多测试10000个小于10000的整数。#include#include#includeintmain(void){intlimit=0;start:printf("请输入上限数（输入0退出）：");scanf("%d",&limit);i

13、f(limit<0

14、

15、limit>100000000){printf("请输入大于1且不大于100000000的自然数");gotostart;}if(limit==0)return0;intmaxp=0;//用来保存最大的素数intcount=2;//用来保存素数个数//freopen("out.txt","w+",stdout);//如果结果需输出到文件，请去掉注释printf("2t3t");clock_tstart,end;//用来计算程序耗时的start=clock();for(inti=4;i<=limit;i++){intss=

16、(int)sqrt(i);for(intt=2;t