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也是质数......
上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了！