python – 素数代码的优化

概述这是我在 python中的代码,用于计算小于给定数字的素数之和. 我还能做些什么来优化它？ import mathprimes = [2,] #primes store the prime numbersfor i in xrange(3,20000,2): #i is the test number 这是我在 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 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 flagsis_prime = [1 for num in xrange(N)]is_prime[0] = 0 # this is because indexing starts at zerois_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 accordinglyfor 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做这个.

总结

以上是内存溢出为你收集整理的python – 素数代码的优化全部内容，希望文章能够帮你解决python – 素数代码的优化所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。