概述
本文研究的主要是Python编程求质数实例,选取了几个数进行了测试,具体如下。
定义:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。
我们知道自然数(除了0和1以外)都可以写成几个质数相乘再乘以一的格式,所以我们可以用以个数去试一试看看它能否将小于它的质数整除。
首先我们创建一个空的list,然后我们知道2是最小的质数,于是我们把2添加进这个空白的list,之后我们开始循环,第一个数从3开始,用3除以小于3的质数,没有小于它的质数能被它整除,我们将3再添加入我们所创建的list,然后循环到4,在list中有一个质数2能将它整除,我们就舍去这个数因为它不是我们所要的质数。后面的以此类推,合数被舍去,质数保存到list中,最后打印出list就是我们所要的质数合集啦。
import time start=time.clock() i=input('please enter an integer:') #创建一个空list r=list() #添加元素2 r.append(2) #从3开始挨个筛选 for a in range(3,i): b=False #用a除以小于a的质数b for b in r: if a%b==0: b=False break else: b=True if b==True: r.append(a) print r t=(time.clock()-start) print t
如下显示:
下面用1000来测试代码的结果:
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
3.29336980871
这段代码需要用到一点点list的知识,(学校上课刚好讲到这里),正好可以练习一下如何添加和调用list中的元素哦!
我们来对比一下最容易想到的的办法的效率
import time start=time.clock() b=False i=input('enter an integer please:') for a in range(2,i): for c in range(2,a): if a%c==0: b=False break else: b=True if b==True: print a,elapsed=(time.clock()-start) print elapsed
运行结果为:
enter an integer please:200
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 2.86033831663
>>>
运行起来明显比前一段代码要迟钝。
下面,使用第一段代码求100000以内的质数,实在是有些卡,下面结果供参考(仅截取了部分结果):
总结
以上就是本文关于Python编程求质数实例代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
总结
以上是编程之家为你收集整理的Python编程求质数实例代码全部内容,希望文章能够帮你解决Python编程求质数实例代码所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧