Python實現高效求解素數代碼實例

 　　這篇文章主要介紹了Python實現高效求解素數代碼實例,本文直接給出代碼實例,需要的朋友可以參考下

　　素數是編程中經常需要用到的。

　　作為學習Python的示例，下面是一個高效求解一個范圍內的素數的程序，不需要使用除法或者求模運算。

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #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