Python实现高效求解素数代码实例_Python

Python实现高效求解素数代码实例

2020-07-18 11:14Python教程网 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