|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
计算质数是学习各种语言常见的题目,在计算时总感觉到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))
复制代码
结果:
速度提高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))
复制代码
结果:
速度又提高了5倍多。
大家看看还可以如何优化。 |
评分
-
查看全部评分
|