此三種方法都是基于試除法揪惦，即不斷地嘗試能否整除遍搞。比如要判斷自然數(shù) x 是否質(zhì)數(shù)，就不斷嘗試小于 x 且大于1的自然數(shù)丹擎，只要有一個能整除尾抑，則 x 是合數(shù)歇父；否則蒂培，x 是質(zhì)數(shù)。
方式1：從 2 一直嘗試到 x-1榜苫。
方式2：從 2 一直嘗試到 x/2护戳。
方式3：從 2 一直嘗試到√x。
代碼部分
import time
import math
def f1(x):
a = []
for i in range(2, x+1):
for j in range(2, i):
if i % j == 0:
break
else:
a.append(i)
# print(a)
def f2(x):
a = []
for i in range(2, x+1):
y = int(i//2+1)
for j in range(2, y):
if i % j == 0:
break
else:
a.append(i)
# print(a)
def f3(x):
a = []
for i in range(2, x+1):
y = int(math.sqrt(i)+1)
for j in range(2, y):
if i % j == 0:
break
else:
a.append(i)
# print(a)
if __name__ == '__main__':
t1 = time.clock()
f1(100)
t2 = time.clock()
print('第一種方式所用時間為{}秒'.format(t2-t1))
t3 = time.clock()
f2(100)
t4 = time.clock()
print('第二種方式所用時間為{}秒'.format(t4-t3))
t5 = time.clock()
f3(100)
t6 = time.clock()
print('第三種方式所用時間為{}秒'.format(t6-t5))
運行結(jié)果
第一種方式所用時間為0.00011377787891367015秒
第二種方式所用時間為0.00010088897856798095秒
第三種方式所用時間為0.0001515556902717247秒
在計算100以內(nèi)質(zhì)數(shù)時三種方法的運算速度差不多垂睬，第二種似乎占據(jù)一定優(yōu)勢媳荒，那來看一看如果不斷增大范圍，三種方法的運行速度到底有多大的差別驹饺。钳枕。。赏壹。鱼炒。。
顯而易見蝌借，在范圍10000之前昔瞧，三種方式差別不大，但在10000以后菩佑，他們之間的差距呈幾何擴大自晰，可得，第三種方法遠遠快于前兩種方法
后續(xù)稍坯，還可以嘗試先將偶數(shù)去除（除2以外）酬荞，再來進行試除，速度一定再上一個臺階瞧哟，當(dāng)然求質(zhì)數(shù)還有其他N種方法混巧，比如篩法，其發(fā)明人是公元前250年左右的一位希臘大啪钗校——埃拉托斯特尼
首先牲剃，2是公認最小的質(zhì)數(shù)，所以雄可，先把所有2的倍數(shù)去掉凿傅；然后剩下的那些大于2的數(shù)里面缠犀，最小的是3，所以3也是質(zhì)數(shù)聪舒；然后把所有3的倍數(shù)都去掉辨液，剩下的那些大于3的數(shù)里面，最小的是5箱残，所以5也是質(zhì)數(shù)......
上述過程不斷重復(fù)滔迈，就可以把某個范圍內(nèi)的合數(shù)全都除去（就像被篩子篩掉一樣），剩下的就是質(zhì)數(shù)了被辑！
