Python---试除法求质数的三种方式对比

简介: 此三种方法都是基于试除法,即不断地尝试能否整除。比如要判断自然数 x 是否质数,就不断尝试小于 x 且大于1的自然数,只要有一个能整除,则 x 是合数;否则,x 是质数。

此三种方法都是基于试除法,即不断地尝试能否整除。比如要判断自然数 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以内质数时三种方法的运算速度差不多,第二种似乎占据一定优势,那来看一看如果不断增大范围,三种方法的运行速度到底有多大的差别。。。。。。

img_03d8abcecea8477508defad6e0bdd4cb.png
三种方式差别

显而易见,在范围10000之前,三种方式差别不大,但在10000以后,他们之间的差距呈几何扩大,可得,第三种方法远远快于前两种方法

后续,还可以尝试先将偶数去除(除2以外),再来进行试除,速度一定再上一个台阶,当然求质数还有其他N种方法,比如筛法,其发明人是公元前250年左右的一位希腊大牛——埃拉托斯特尼
首先,2是公认最小的质数,所以,先把所有2的倍数去掉;然后剩下的那些大于2的数里面,最小的是3,所以3也是质数;然后把所有3的倍数都去掉,剩下的那些大于3的数里面,最小的是5,所以5也是质数......
上述过程不断重复,就可以把某个范围内的合数全都除去(就像被筛子筛掉一样),剩下的就是质数了!

目录
相关文章
|
7月前
|
Python
Python质数判断
Python质数判断
|
7月前
|
算法 Python
python:判断一个数是否为质数
python:判断一个数是否为质数
|
7月前
|
Java C++ Python
Python 教程之运算符(5)—— Python中的除法运算符
Python 教程之运算符(5)—— Python中的除法运算符
79 0
|
2月前
|
Python
Python - 获取 100 以内的质数
Python - 获取 100 以内的质数
|
7月前
|
Python
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
如何判断一个数是质数? 要求:编写一个Python函数,输入一个整数,输出该整数是否为质数。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。
368 1
|
6月前
|
Python
Python中除法和不支持除法的类型
【6月更文挑战第3天】
43 3
|
7月前
|
Python
用python打印前100个最小的质数
用python打印前100个最小的质数
118 1
|
7月前
|
Python
python打印质数
python打印质数
77 2
|
7月前
|
Python
用python打印前100个最小的质数
用python打印前100个最小的质数
105 2
|
7月前
|
Go Python Java
Python每日一练(20230413) 最后一个单词长度、全排列、计数质数
Python每日一练(20230413) 最后一个单词长度、全排列、计数质数
63 0
Python每日一练(20230413) 最后一个单词长度、全排列、计数质数