一阳谍、素數(shù)的定義
? 質(zhì)數(shù)（prime number）又稱素數(shù)炫欺，有無限個迂猴。除了1和它本身以外不再有其他的除數(shù)整除扁凛。從定義知道盾沫；1不是素數(shù)，最小的素數(shù)是2殿漠。
二赴精、N以內(nèi)素數(shù)常用實現(xiàn)方法
? 首先教科書寫法（暫時不做任何代碼優(yōu)化）：
import math
def prime(n):
if n <= 1:
return 0
#for i in range(2,int(math.sqrt(n)+1)):
for i in range(2,n):
if n%i == 0:
return 0
return 1
if __name__ == "__main__":
n = int(input(">>"))
for i in range(2,n+1):
if prime(i):
print (i)
? 代碼中注釋行是取了[2,√n+1]作為除數(shù)范圍，通過對比測試绞幌，顯然蕾哟，[2,√n+1]范圍下，效率快了很多莲蜘。
三谭确、優(yōu)化方法
原理層面
? 1、除了2以外票渠，其余的偶數(shù)顯然不可能是素數(shù)逐哈，再來看奇數(shù)，1不是素數(shù)问顷，從3開始看昂秃，除了3以外，其余能被3整除的都是合數(shù)择诈，再看5械蹋，除了5以外出皇，其余能被5整除的都是合數(shù)，加起來郊艘，一共在[2,√n+1]范圍內(nèi)排除了近3/4的計算量荷科。
? 2、另外使用埃拉托斯特尼篩法（希臘語：κ?σκινον ?ρατοσθ?νου?纱注，英語：sieve of Eratosthenes ）畏浆，簡稱埃氏篩，也有人稱素數(shù)篩狞贱。這是一種簡單且歷史悠久的篩法刻获，用來找出一定范圍內(nèi)所有的素數(shù)。
所使用的原理是從2開始瞎嬉，將每個素數(shù)的各個倍數(shù)蝎毡，標(biāo)記成合數(shù)。一個素數(shù)的各個倍數(shù)氧枣，是一個差為此素數(shù)本身的等差數(shù)列沐兵。
算式：
給出要篩數(shù)值的范圍n，找出\sqrt{n}以內(nèi)的素數(shù) p1,p2,...,pk
先用2去篩便监，即把2留下扎谎，把2的倍數(shù)剔除掉碳想；再用下一個素數(shù)，也就是3篩毁靶，把3留下胧奔，把3的倍數(shù)剔除掉；接下去用下一個素數(shù)5篩预吆，把5留下葡盗，把5的倍數(shù)剔除掉；不斷重復(fù)下去......啡浊。
def eratosthenes(n):
IsPrime = [True] * (n + 1)
IsPrime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if IsPrime[i]:
for j in range(i * 2, n + 1, i):
IsPrime[j] = False
return {x for x in range(2, n + 1) if IsPrime[x]}
if __name__ == "__main__":
print (eratosthenes(n))
代碼層面
第一種優(yōu)化思路：
import math
def prime(n):
if n%2 == 0:
return n==2
if n%3 == 0:
return n==3
if n%5 == 0:
return n==5
for p in range(7,int(math.sqrt(n))+1,2): #只考慮奇數(shù)作為可能因子
if n%p == 0:
return 0
return 1
if __name__ == "__main__":
n = int(input(">>"))
for i in range(2,n+1): #1不是素數(shù),從2開始
if prime(i):
print i
? 再來實現(xiàn)第二種思路觅够，代碼如下：
#尋找n以內(nèi)的素數(shù)，看執(zhí)行時間巷嚣，例子100000內(nèi)的素數(shù)
def prime(n):
flag = [1]*(n+2)
p=2
while(p<=n):
print p
for i in range(2*p,n+1,p):
flag[i] = 0
while 1:
p += 1
if(flag[p]==1):
break
# test
if __name__ == "__main__":
n = int(input(">>"))
prime(n)
統(tǒng)一測試下差異很清楚喘先。第二種方法要優(yōu)于第一種，再優(yōu)化下代碼
首先廷粒，將range換成xrange窘拯，再測試下：兩種方法速度都有提升。range和xrange的差異坝茎，range是一次性連續(xù)返回一個列表涤姊，而xrange是每次只生成一個，并且不保留上次生成的值嗤放。
?致命錯誤:
對于range(2*p,n+1,p)思喊，還有一種實現(xiàn)方法，range(2*p,n+1)[::p]次酌，但這兩種寫法恨课，完全不相干，range(2*p,n+1,p)返回的列表就是按照p步長來生成的岳服，而range(2*p,n+1)[::p]剂公，是生成了步長為1的列表，最后列表執(zhí)行切片操作吊宋，只取p步長的值返回纲辽，顯然沒有range(2*p,n+1,p)的實現(xiàn)更為直接，兩者雖然返回值一樣璃搜，但經(jīng)過實際測試發(fā)現(xiàn)拖吼，效率差異非常大，甚至可以顛覆算法的優(yōu)勢腺劣。
?在這幾種方案中绿贞，最后一種速度最快，效率最高橘原，但有個應(yīng)用前提籍铁，就是待搜索列表必須是有序且連續(xù)的涡上，所以比較適合N以內(nèi)符合某條件的數(shù)字。
