程序优化提高计算质数的效率

冬雪雪冬

计算质数是学习各种语言常见的题目，在计算时总感觉到python运算速度比较慢，其实通过算法的优化可以显著提高速度，下面就以几种方法的差别。
程序1：

from time import time
start = time()
result = [2] #把第一个质数先放到列表中，主要是考虑其它质数都是奇数
for i in range(3, 100000):
    isPrime = True #这里设置一个标记flag，先假定是质数，后面判断如果不是再修改
    for j in range(2, i): 
        if i % j == 0: #用2到i-1的数依次去计算
            isPrime = False
            break
    if isPrime == True: #如果是质数加到列表中
        result.append(i) 
print('10万以内总共%d个质数'%len(result))
print('花费时间%.2f秒'%(time() - start))

加上一个time函数计算用时。
结果是：

10万以内总共9592个质数
花费时间102.68秒

用时近2分钟，这里没有把每个质数打印出来，主要考虑在idle中print用时较长，结果不单单是运算的时间。

程序2：
我们看看有哪些可以优化的。
4行，i只能是奇数（偶数必然能被2整除），所以计算范围改为range(3, 100000, 2)，这样差不多把计算量减少一半。
5行取消，不需要标记，python的循环有一个else语句，当循环没有break退出，而是完全执行完循环，则执行循环后面的else语句。
j的取值范围也要优化，j不会超过i的平方根，以14为例，7是它的因子，超过了14的平方根，但必然有一个2是小于14平方根的因子。

from time import time
from math import sqrt
start = time()
result = [2]
for i in range(3, 100000, 2):
    for j in range(2, int(sqrt(i)) + 1):
        if i % j == 0:
            break
    else:
        result.append(i) 
print('10万以内总共%d个质数'%len(result))
print('花费时间%.2f秒'%(time() - start))

结果：

10万以内总共9592个质数
花费时间0.45秒

速度提高200多倍。

程序3：
如果一个数不能被3整除，那么必然不能被3的倍数整除，所以判断3后，就不用再算3的倍数了，这样只要用已经算的的质数作为j就可以了。

from time import time
start = time()
result = [2]
for i in range(3, 100000, 2):
    for j in result:
        if i % j == 0 or j * j > i:
            break
    else:
        result.append(i) 
print('10万以内总共%d个质数'%len(result))
print('花费时间%.2f秒'%(time() - start))

结果：

10万以内总共4个质数
花费时间0.08秒

速度又提高了5倍多。

大家看看还可以如何优化。

wp231957

python控制excel   和vba控制excel
哪个更快些？

冬雪雪冬

wp231957 发表于 2021-9-16 17:55
python控制excel   和vba控制excel
哪个更快些？

应该是vbs更快些

yalie

感谢楼主无私奉献！

lightninng

版主好，感觉版面好冷清啊。我来加点人气。。。

感觉这是道数学题而不是编程题，基本上就是依靠数学知识来减少迭代次数的游戏，想到一个改进点，任何合数都是由若干质数相乘得到的，那么一个合数必然是有一个小于他的平方根的质数作为他的约数。
说人话就是，我们迭代的范围可以缩小到已经找到的质数里小于这个数的平方根的所有数中。
综上，代码如下

from math import sqrt

def judge_3(num):
    # 本函数从所有小于平方根的数中进行迭代
    p_list=[2,3]
    for i in range(5,num+1,2):
        for j in range(2,int(sqrt(i))+1):
            if i%j==0:
                break
        else:
            p_list.append(i)


def judge_4(num):
    # 本函数从已有的质数里小于平方根的数中进行迭代
    p_list=[2,3]
    for i in range(5,num+1,2):
        flag=False
        for j in p_list:
            if j > sqrt(i):
                flag=True
                break
            if i%j==0:
                break
        else:
            flag=True

        if flag:
            p_list.append(i)

t=time.time()
for i in range(10):
    judge_3(100000)
print(f"{time.time()-t}")

t=time.time()
for i in range(10):
    judge_4(100000)
print(f"{time.time()-t}")

运行结果如下：

=============== RESTART: C:\Users\lightninng\Desktop\list_2021.py ==============
1.6769840717315674
1.5121424198150635
>>> 

可以看到提升非常有限，代码逻辑应该也有优化空间，不过熬夜久了，脑袋有点转不动了，就这样吧。哈哈哈哈哈。。尽力了，这种问题还得学数学的来~~~

18408238295