素数代码的优化

Question

素数代码的优化

3

这是我用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,)

- tarashish

2

将 if isprime == True: 替换为 if isprime:。 - mike jones

1

根据建议修改了代码。还有什么建议可以让它更快吗？对于更大的数字，它仍然比较慢。 - tarashish

5个回答

4

您可以优化的另一件事是将sqrt计算移至内部循环之外。毕竟，i 在整个内部循环中保持不变，因此没有必要每次重新计算sqrt（i）。

- Eli Bendersky

3

primes = primes + (i,) 这句话非常耗费时间。每次循环都会复制所有元素，将您优雅的动态编程解决方案转换为一个O(N²)算法。使用列表来代替：

primes = [2]
...
    primes.append(i)

此外，在通过sqrt(i)后及早退出循环。由于在运行到质数列表的末尾之前保证会通过sqrt(i)，因此应该就地更新列表而不是存储isprime以供以后使用：

...
if j > math.sqrt(i):
    primes.append(i)
    break
if i%j == 0:
    break
...

最后，虽然这与性能无关，但更符合Python风格的做法是使用range而不是while：

for i in range(3, 10000, 2):
    ...

- Marcelo Cantos

2

反正它的时间复杂度是 O(n^2)，但当然最好还是摆脱元组。比使用primes.append()更快的方法是即时计算总和，根本不需要存储质数。 - Sven Marnach

1

如果他正在使用Python2.x，最好也使用xrange。 - Thomas Orozco

1

@Sven：如果他不存储质数，那么进行质数检查会更加困难。 - Thomas Orozco

1

@Thomas 是的，我正在使用 Python 2.7...虽然我不太熟悉 xrange..但我会在文档中查找它..还有一个问题..我是否应该总是使用 list 而不是 tuples? 并且没有任何方法可以向 tuple 中添加元素吗？ - tarashish

@SvenMarnach：是的，你说得对。我是根据我的回答建议来思考的。 - Marcelo Cantos

显示剩余6条评论

1

只是另一段没有使用任何导入的代码：

#This will check n, if it is prime, it will return n, if not, it will return 0
def get_primes(n):
    if n < 2:
        return 0
    i = 2
    while True:
        if i * i > n:
            return n
        if n % i == 0:
            return 0
        i += 1

#this will sum up every prime number up to n
def sum_primes(n):
    if n < 2:
        return 0
    i, s = 2, 0
    while i < n:
        s += get_primes(i)
        i += 1
    return s

n = 1000000
print sum_primes(n)

- Arnaldo P. Figueira Figueira

0

编辑：在受影响时删除了一些愚蠢的内容

所有暴力类型的算法，无论多么高效，用于查找质数的上限增加时都会变得极其昂贵。启发式方法可以实际节省大量计算来测试素性。已建立的可除规则可以“一眼”消除大多数非质数。

- shimofuri

这是一个非常糟糕的想法。链接页面只显示了对于集合，包含测试更快，而上述代码并没有使用这样的测试。大多数其他操作实际上对于集合来说更慢。最重要的是，我们将失去质数的顺序，因此我们不能再在达到平方根时退出循环。 - Sven Marnach

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- taleinat · Accepted Answer

你可以使用一种名为埃拉托色尼筛法的不同算法，它速度更快但需要更多的内存。保持一个标志数组，表示每个数字是质数还是非质数，对于每个新的质数，将其所有倍数都设为零。

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]]

如果您使用高效的位数组，例如在此示例中所示（滚动到页面下方，您会发现Eratosthenes筛选器的示例），即使对于很大的N，也可以实现这一点。