今天我解决了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)
这是它的可视化。