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

我們浪費空間來避免浪費時間。但是，再次，對於這個範圍的數字，這是不值得的。