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