1

今天我解决了Project Euler中给出的一个问题，它是第 10 个问题，我的 python 程序花了7 个小时才显示结果。但是在那个论坛本身，一个名叫lassevk的人为此发布了解决方案，只用了4 秒。我不可能在那个论坛上发布这个问题，因为它不是一个讨论论坛。因此，如果您想将此问题标记为非建设性问题，请考虑这一点。

marked = [0] * 2000000
value = 3
s = 2
while value < 2000000:
    if marked[value] == 0:
        s += value
        i = value
        while i < 2000000:
            marked[i] = 1
            i += value
    value += 2
print s

如果有人理解此代码，请尽可能简单地解释它。

这是我的代码，计算时间为 7 小时（我想我也使用了与以下答案中提到的 Eratosthenes 筛法相同的逻辑）：

import time
start = time.clock()

total = 0
limit = 2000000
KnownPrime = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
                  53, 59, 61, 67, 71])
KnownPrime.update(set([73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
                       131, 137, 139, 149, 151, 157, 163, 167, 173]))
suspected = set(range(2, limit+1)) # list of suspected prime numbers
for p in KnownPrime:
    if p <= limit:
        total += p
        suspected.difference_update(set(range(p, limit+1, p)))

for i in suspected:
    k = i/2
    if k % 2 == 0: k += 1
    PrimeCheck = set(range(k, 2, -2))
    PrimeCheck.difference_update(KnownPrime)
    for j in PrimeCheck:
        if i % j == 0:
            break
    if i % j:
        total += i

print time.clock() - start
print total

所以，谁能告诉我为什么花了这么多时间。

最后我做到了，这是我重构的代码。现在它可以在 2 秒内显示结果。

import math
import __builtin__

sum = __builtin__.sum

def is_prime(num):
    if num < 2: return False
    if num == 2: return True
    if num % 2 == 0: return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0: return False
    return True

def sum_prime(num):
    if num < 2: return 0
    sum_p = 2
    core_primes = []
    suspected = set(range(3, num + 1, 2))
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if is_prime(i): core_primes.append(i)
    for p in core_primes:
        sum_p += p
        suspected.difference_update(set(range(p, num + 1, p)))
    return sum(suspected) + sum_p

print sum_prime(2000000)

这是它的可视化。

4

4 回答 4

4

问题：

求两百万以下的所有素数之和。

这是一个简单的筛子。您应该阅读它，但一般的想法是遍历每个数字 - 如果索引号的值是0，它是质数，并且您标记该数字的倍数（因为所有这些倍数都不能是质数）。如果是1（复合）则忽略。我将提供一些注释来解释这段代码具体在做什么，

marked = [0] * 2000000     # <- just set up the list
value = 3                  # <- starting at 3 then checking only odds
s = 2                      # <- BUT include 2 since its the only even prime
while value < 2000000:
    if marked[value] == 0: # <- if number at index value is 0 it's prime
        s += value         #    so add value to s (the sum)
        i = value          # <- now mark off future numbers that are multiples of
        while i < 2000000: #    value up until 2mil
            marked[i] = 1  # <- number @ index i is a multiple of value so mark
            i += value     # <- increment value each time (looking for multiples)
    value += 2             # <- only check every odd number
print s

此代码的两个优化：

  1. 的初始值i可以设置为value*value==value**2
  2. 可以轻松地将其更改为使用长度为 100 万的列表，因为我们已经知道没有偶数是素数

编辑：

虽然我希望我的回答有助于为未来的访问者解释筛子的操作，但如果您正在寻找一个非常快速的筛子实现，请参考这个问题。unutbu 的出色性能分析和 Robert William Hanks 发布的一些优秀算法！

于 2013-06-25T04:15:32.367 回答
1

该代码基本上是使用Eratosthenes 的筛子来查找素数，一旦您取出跟踪总和的代码，这可能会更清楚：

marked = [0] * 2000000
value = 3
while value < 2000000:
    if marked[value] == 0:
        i = value
        while i < 2000000:
            marked[i] = 1
            i += value
    value += 2

value增加 2 （因为你知道所有高于 2 的偶数都不是素数，你可以跳过它们）并且任何value在你到达它时还没有被标记的都是素数，因为你已经标记了所有它下面的值的倍数。

于 2013-06-25T04:13:52.180 回答
1

这段代码基本上使用 Eratosthenes 的筛法概念总结了所有 < 2000000 的素数：

标记的是一个充满零的巨大数组。

每次小于 2000000 时，检查标记的数组中的值是否被标记。标记可以视为将数组位置标记为 1。例如，如果要标记一个值，则将该值在标记数组中的位置标记为 1（其余均为零）。

接下来，将 i 设置为该值（i 是您用于 while 循环的值）。当 i 小于 2000000 时，标记该特定值的标记数组。然后将 i 增加该值。这样做是为了：如果您标记所有 2 的倍数，则无需在下一次迭代中重复所有这些。例如。如果你标记了 2 的所有倍数，下一步你可以从 3^2 = 9 开始为 3，因为到那时所有较小的倍数都已经被标记了。

有关详细信息，请参阅Eratosthenes 筛和此视频。

于 2013-06-25T04:17:42.260 回答
0

这个答案是使用Erastothenes 的筛法来标记非素数（这就是marked列表的用途），然后通过并仅添加尚未标记的值。有关更多详细信息，请参阅维基百科文章。

于 2013-06-25T04:15:10.780 回答