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

スポイラーALERT：以下はプロジェクトオイラーで10を質問に対する回答が含まれています。

問題は、実行するには時間がかかりすぎることです。これは、あまりにも多くのチェックが行われていて、処理に時間がかかりすぎるためです。 PEの質問では、通常は、結果を十分に速くするためにプログラムを手に入れるというトリックを考えなければなりません。この場合、素数が数の平方根より大きい素数で割り切れる天気をチェックする必要がない理由を理解する必要があります。

pはの平方根よりも大きい場合には数xは、n = x/pある自然数nがあることを意味するであろうこと、xの平方根よりも大きい素数pで割り切れた場合xならばnはxの平方根より小さい（なぜこれが真だと思うか）。つまり、xという数字は、nという数字で割り切れ、それはxの平方根よりも小さくなります。つまり、xは、xの平方根より小さいすべての数値をチェックしたときにn（またはnの素因数）で割り切れることが判明しているので、それ以上の数値をチェックする必要はありません数の平方根は、それが素数QEDかどうかを知るためのものです。

このようにして、多くの計算量を節約できます。以下は、このアイデアを実装Pythonプログラムである：私は@DonatPantsで詳細な回答に感謝して

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

同じくらい、私は解決策があまりにも複雑であると信じています。最初に、より単純な正方形が行う場合、sqrt()を計算する必要はありません（つまり、方程式の両辺を正方形にします）.2番目のテストの順番が逆になります。なぜprime > sqrtの後にif number % prime == 0をチェックしますか？ prime > sqrtの場合、もう1つのテストは必要ありません。そしてそのブール値は何ですか？この問題への私の単純なアプローチ：

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

時間を無駄にしないようにスペースを浪費しています。しかし、再びこの数字の範囲では、それは価値がありません。