c语言求素数问题算法

c语言求素数问题算法

ID:6732874

大小:72.00 KB

页数:8页

时间:2018-01-23

c语言求素数问题算法_第1页
c语言求素数问题算法_第2页
c语言求素数问题算法_第3页
c语言求素数问题算法_第4页
c语言求素数问题算法_第5页
资源描述:

《c语言求素数问题算法》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、如何求素数1.自然数是0,1,2……2.素数是2,3,5……(不包括1的只能背1和它本身整除的自然数) #include#includevoidmain(){inti,j,flag=1;for(i=101;i<200;i++){flag=1;for(j=2;j<=sqrt(200);j++)if(i%j==0){flag=0;break;}if(flag==1)printf("i=%d是素数",i);}}【1】求10000以内的所有素数。素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表

2、示所有的素数,所以对于数学家来说,素数一直是一个未解之谜。像著名的哥德巴赫猜想、孪生素数猜想,几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研,呕心沥血,但至今仍然未见分晓。自从有了计算机之后,人们借助于计算机的威力,已经找到了2216091以内的所有素数。求素数的方法有很多种,最简单的方法是根据素数的定义来求。对于一个自然数N,用大于1小于N的各个自然数都去除一下N,如果都除不尽,则N为素数,否则N为合数。但是,如果用素数定义的方法来编制计算机程序,它的效率一定是非常低的,其中有许多地方都值得改进。第一,对于一个自然数N,只要能被一个非1非

3、自身的数整除,它就肯定不是素数,所以不必再用其他的数去除。第二,对于N来说,只需用小于N的素数去除就可以了。例如,如果N能被15整除,实际上就能被3和5整除,如果N不能被3和5整除,那么N也决不会被15整除。第三,对于N来说,不必用从2到N一1的所有素数去除,只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明:如果N是合数,则一定存在大于1小于N的整数d1和d2,使得N=d1×d2。如果d1和d2均大于√N,则有:N=d1×d2>√N×√N=N。而这是不可能的,所以,d1和d2中必有一个小于或等于√N。基于上述分析,设计算法如

4、下:(1)用2,3,5,7逐个试除N的方法求出100以内的所有素数。(2)用100以内的所有素数逐个试除的方法求出10000以内的素数。首先,将2,3,5,7分别存放在a[1]、a[2]、a[3]、a[4]中,以后每求出一个素数,只要不大于100,就依次存放在A数组中的一个单元中。当我们求100—10000之间的素数时,可依次用a[1]-a[2]的素数去试除N,这个范围内的素数可以不保存,直接打印。【2】用筛法求素数。简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家,他在寻找素数时,采用了一种与众不同的方法:先将2-N的各数写在纸上:在2的上面画一

5、个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数是5,将它画圈,并划去5的其他倍数……依次类推,一直到所有小于或等于N的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于N的素数。这很像一面筛子,把满足条件的数留下来,把不满足条件的数筛掉。由于这种方法是厄拉多塞首先发明的,所以,后人就把这种方法称作厄拉多塞筛法。在计算机中,筛法可以用给数组单元置零的方法来实现。具体来说就是:首先开一个数组:a[i],i=1,2,3,…,同时,令所有的数组元素都等于下

6、标值,即a[i]=i,当i不是素数时,令a[i]=0。当输出结果时,只要判断a[i]是否等于零即可,如果a[i]=0,则令i=i+1,检查下一个a[i]。筛法是计算机程序设计中常用的算法之一。【3】用6N±1法求素数。任何一个自然数,总可以表示成为如下的形式之一:6N,6N+1,6N+2,6N+3,6N+4,6N+5(N=0,1,2,…)显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。根据上述分析,我们可以构造另一面

7、筛子,只对形如6N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。在程序上,我们可以用一个二重循环实现这一点,外循环i按3的倍数递增,内循环j为0-1的循环,则2(i+j)-1恰好就是形如6N±1的自然数。浅析求素数算法注意:如果没有特殊说明,以下讨论的都是针对n为素数时的时间复杂度1.根据概念判断:如果一个正整数只有两个因子,1和p,则称p为素数.代码:时间复杂度O(n).boolisPrime(intn){if(n<2)returnfalse;for(inti=2;i

8、rnfalse;returntrue;}2.改进,去掉偶数的判断代码:时间复杂度O(n/2),

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。