python – 素数代码的优化
发布时间:2020-12-20 12:27:20 所属栏目:Python 来源:网络整理
导读:这是我在 python中的代码,用于计算小于给定数字的素数之和. 我还能做些什么来优化它? import mathprimes = [2,] #primes store the prime numbersfor i in xrange(3,20000,2): #i is the test number x = math.sqrt(i) isprime = True for j in primes: #j
这是我在
python中的代码,用于计算小于给定数字的素数之和.
我还能做些什么来优化它? import math primes = [2,] #primes store the prime numbers for i in xrange(3,20000,2): #i is the test number x = math.sqrt(i) isprime = True for j in primes: #j is the devider. only primes are used as deviders if j <= x: if i%j == 0: isprime = False break if isprime: primes.append(i,) print sum (primes,) 解决方法
您可以使用另一种称为
Sieve of Eratosthenes的算法,该算法速度更快但占用更多内存.保留一组标志,表示每个数字是否为素数,并且对于每个新素数集,它对于该素数的所有倍数都为零.
N = 10000 # initialize an array of flags is_prime = [1 for num in xrange(N)] is_prime[0] = 0 # this is because indexing starts at zero is_prime[1] = 0 # one is not a prime,but don't mark all of its multiples! def set_prime(num): "num is a prime; set all of its multiples in is_prime to zero" for x in xrange(num*2,N,num): is_prime[x] = 0 # iterate over all integers up to N and update the is_prime array accordingly for num in xrange(N): if is_prime[num] == 1: set_prime(num) primes = [num for num in xrange(N) if is_prime[num]] 如果使用有效的位数组,例如在this example中(在页面上向下滚动,你将找到一个Sieve of Eratosthenes示例),你实际上可以为相当大的N做这个. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- 浅谈机器学习需要的了解的十大算法
- 无法在Ubuntu 16.04.5中安装Geograpy python软件包
- Django CSRF Coo??kie – 为什么它不会在浏览器关闭时到期?
- windows上安装Anaconda和python的教程详解
- 讲实话,我会Python之后!我都不屑用PS了!Python抠图太方便
- python – 创建realy巨大的scipy数组
- Python3 循环语句(for、while、break、range等)
- python – Django获取许多ID的对象
- Python写的网站C段扫描工具
- python – django.db.utils.IntegrityError:重复键值违反唯