Python脚本未完成

Question

我试图运行我的代码以尝试解决第10号欧诺问题。我对Python非常陌生，我的代码一直非常缓慢，在这种情况下永远不会结束。任何帮助，将不胜感激。谢谢。

primes = [2] 
number = 2 

y=1 
while y <=1: 
    for i in primes: 
     if number % i == 0: 
      break 
     else: 
      if i == primes[-1]: 
       primes.append(number) 
       if (primes[-1]) >= 2000000: 
        del primes[-1] 
        y += 2 
    number+=1 
print(sum(primes)) 

Answer 1

SPOILER ALERT：以下包含Project Euler中问题10的答案。

您的问题是您的代码运行时间过长，这是因为它检查了太多东西，并且需要很长时间才能运行。在PE问题中，你通常不得不考虑让你的程序足够快地获得结果。在这种情况下，您需要了解为什么不需要检查天气素数可以被数字平方根大的素数整除。

如果数字x是一个素数p比的x平方根更大的整除，这将意味着有一个自然数n即n = x/p，如果p比的平方根更大x然后n小于x的平方根（想想为什么这是真的）。这意味着我们会发现数字x也可以被n整除，该数字小于x的平方根。这意味着当我们检查所有小于x的平方根的数字时，我们已经发现x可以被n（或n的一个主要因子）整除，因此不需要检查任何大于一个数字的平方根是为了知道它是否为素数QED。

这样你可以节省很多的计算。下面是实现这个想法python程序：

import math 

primes = [2] 
is_prime = True 

# loop over all the ODD numbers from 3 to 2,000,000 (no need to check even numbers) 
for number in xrange(3, 2000000 + 1, 2): 
    sqrt = math.sqrt(number) 
    # loop over all the primes we have so far 
    for prime in primes: 
     # if the number we are checking is divisible by a prime it is not prime and we can move on to the next number 
     if number % prime == 0: 
      # we set this value to false so that when we finish the loop we will be able to know if the number is prime or not 
      is_prime = False 
      break 

     # this line is where the clever part is, if we already checked `all the primes that are smaller than square root of x, and we did not find any primes that our number is divisible by, then we will not find any primes higher than the square root of the number that the number is divisible by` 
     if prime > sqrt: 
      break 

    if is_prime: 
     primes.append(number) 
    else: 
     is_prime = True 

# we are done, print the answer 
print sum(primes) 

Answer 2

虽然我很欣赏@DonatPants了详细的解答，我认为，解决办法是太复杂了。首先，我们不需要计算sqrt()，当更简单的平方会做（即方程两边的平方）。第二个测试顺序似乎是落后的，为什么在if number % prime == 0之后检查prime > sqrt？如果prime > sqrt，你不需要其他测试。那布尔值是什么？我简单的方法解决这个问题：

primes = [2] 

for number in range(3, 2000000 + 1, 2): # only test odd numbers 

    for prime in primes: 
     if prime * prime > number: # we're past sqrt, a prime! 
      primes.append(number) 
      break 

     if number % prime == 0: # a composite 
      break 

print(sum(primes)) 

将冗余计算prime * prime是一个低效率。它对这个数字范围并没有什么区别，但是如果需要的话，你可以保留一个单独的正方形数组，枚举素数并使用生成的索引来访问正方形，当你保存素数的时候可以保存这个正方形。只是将素数平方比所有数字的平方根便宜：

primes = [2] 
squares = [4] 

for number in range(3, 2000000 + 1, 2): 

    for index, prime in enumerate(primes): 
     if squares[index] > number: 
      primes.append(number) 
      squares.append(number * number) 
      break 

     if number % prime == 0: 
      break 

print(sum(primes)) 

我们浪费空间来避免浪费时间。但是，再次，对于这个范围的数字，这是不值得的。