Python---試除法求質數的三種方式對比

此三種方法都是基于試除法，即不斷地嘗試能否整除。比如要判斷自然數 x 是否質數，就不斷嘗試小于 x 且大于1的自然數，隻要有一個能整除，則 x 是合數；否則，x 是質數。

方式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))
           

運作結果

第一種方式所用時間為0.00011377787891367015秒

第二種方式所用時間為0.00010088897856798095秒

第三種方式所用時間為0.0001515556902717247秒

在計算100以内質數時三種方法的運算速度差不多，第二種似乎占據一定優勢，那來看一看如果不斷增大範圍，三種方法的運作速度到底有多大的差别。。。。。。

三種方式差别

顯而易見，在範圍10000之前，三種方式差别不大，但在10000以後，他們之間的差距呈幾何擴大，可得，第三種方法遠遠快于前兩種方法

後續，還可以嘗試先将偶數去除（除2以外），再來進行試除，速度一定再上一個台階，當然求質數還有其他N種方法，比如篩法，其發明人是公元前250年左右的一位希臘大牛—— 埃拉托斯特尼

首先，2是公認最小的質數，是以，先把所有2的倍數去掉；然後剩下的那些大于2的數裡面，最小的是3，是以3也是質數；然後把所有3的倍數都去掉，剩下的那些大于3的數裡面，最小的是5，是以5也是質數......

上述過程不斷重複，就可以把某個範圍内的合數全都除去（就像被篩子篩掉一樣），剩下的就是質數了！