Python实现高效求解素数的方法

Python实现高效求解素数的方法是如何来实现的呢?下面的内容将会通过具体的实例来演示Python实现高效求解素数的方法的实现方法及相关技巧:

素数是编程中经常需要用到的。

作为学习Python的示例,下面是一个高效求解一个范围内的素数的程序,不需要使用除法或者求模运算。

#coding:utf-8 #设置python文件的编码为utf-8,这样就可以写入中文注释
def primeRange(n):
myArray=[1 for x in range(n+1)] ##列表解析,生成长度为(n+1)的列表,每个数值都为1
myArray[0]=0
myArray[1]=0
startPos=2
while startPos <= n: if myArray[startPos]==1: key=2 resultPos = startPos * key #可知startPos的整数倍都不是素数,设置startPos的整数倍的位置为0表示非素数 while resultPos <= n: myArray[resultPos] =0 key += 1 resultPos = startPos *key startPos += 1 resultList=[] ##将最终的素数保存在resultList列表返回 startPos=0 while startPos <= n: if myArray[startPos] == 1: resultList.append(startPos) startPos += 1 return resultList numString=raw_input("Input the Range(>3):”)
numInt=int(numString)
if numInt <= 3: print "The Number Need to be greater than 3" else: primeResult=primeRange(numInt) print "The Result is:",primeResult [/code]
Python实现高效求解素数的方法就是这样,欢迎大家参考。。。。

You might also like:

Sidebar