鱼C论坛

 找回密码
 立即注册
查看: 35|回复: 3

[技术交流] 程序优化提高计算质数的效率

[复制链接]
发表于 6 天前 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
计算质数是学习各种语言常见的题目,在计算时总感觉到python运算速度比较慢,其实通过算法的优化可以显著提高速度,下面就以几种方法的差别。
程序1:
  1. from time import time
  2. start = time()
  3. result = [2] #把第一个质数先放到列表中,主要是考虑其它质数都是奇数
  4. for i in range(3, 100000):
  5.     isPrime = True #这里设置一个标记flag,先假定是质数,后面判断如果不是再修改
  6.     for j in range(2, i):
  7.         if i % j == 0: #用2到i-1的数依次去计算
  8.             isPrime = False
  9.             break
  10.     if isPrime == True: #如果是质数加到列表中
  11.         result.append(i)
  12. print('10万以内总共%d个质数'%len(result))
  13. print('花费时间%.2f秒'%(time() - start))
复制代码

加上一个time函数计算用时。
结果是:
  1. 10万以内总共9592个质数
  2. 花费时间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平方根的因子。
  1. from time import time
  2. from math import sqrt
  3. start = time()
  4. result = [2]
  5. for i in range(3, 100000, 2):
  6.     for j in range(2, int(sqrt(i)) + 1):
  7.         if i % j == 0:
  8.             break
  9.     else:
  10.         result.append(i)
  11. print('10万以内总共%d个质数'%len(result))
  12. print('花费时间%.2f秒'%(time() - start))
复制代码

结果:
  1. 10万以内总共9592个质数
  2. 花费时间0.45秒
复制代码

速度提高200多倍。

程序3:
如果一个数不能被3整除,那么必然不能被3的倍数整除,所以判断3后,就不用再算3的倍数了,这样只要用已经算的的质数作为j就可以了。
  1. from time import time
  2. start = time()
  3. result = [2]
  4. for i in range(3, 100000, 2):
  5.     for j in result:
  6.         if i % j == 0 or j * j > i:
  7.             break
  8.     else:
  9.         result.append(i)
  10. print('10万以内总共%d个质数'%len(result))
  11. print('花费时间%.2f秒'%(time() - start))
复制代码


结果:
  1. 10万以内总共4个质数
  2. 花费时间0.08秒
复制代码

速度又提高了5倍多。

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

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
傻眼貓咪 + 1 + 1 感谢楼主无私奉献!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 5 天前 From FishC Mobile | 显示全部楼层
python控制excel   和vba控制excel
哪个更快些?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 5 天前 | 显示全部楼层
wp231957 发表于 2021-9-16 17:55
python控制excel   和vba控制excel
哪个更快些?

应该是vbs更快些
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
感谢楼主无私奉献!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2021-9-21 09:44

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表