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 回答