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時間かかった私のコードです（以下の回答で言及されているエラトステネスのふるい手法と同じロジックも使用したと思います）：

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

質問：

200 万未満のすべての素数の合計を求めます。

簡易ふるいです。それについて読む必要がありますが、一般的な考え方は、各数値を反復することです-インデックス番号の値が の場合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

このコードの 2 つの最適化:

  1. の初期値は==iに設定できますvalue*valuevalue**2
  2. 偶数が素数ではないことはすでにわかっているので、長さ 100 万のリストを使用するようにこれを簡単に変更できます。

編集：

私の回答が将来の訪問者のためにふるいの操作を説明するのに役立つことを願っていますが、非常に高速なふるいの実装を探している場合は、この質問を参照してください。unutbu による優れたパフォーマンス分析と、Robert William Hanks によって投稿されたいくつかの優れたアルゴリズム!

于 2013-06-25T04:15:32.367 に答える
1

このコードは基本的に、エラトステネスのふるいの概念を使用して、2000000 未満のすべての素数を合計します。

Marked は、ゼロでいっぱいの巨大な配列です。

値が 2000000 未満になるたびに、マークされた配列の値にフラグが設定されているかどうかを確認します。フラグ付けは、配列の位置を 1 としてマークすることと見なすことができます。たとえば、値にフラグを付けたい場合は、マークされた配列内のその値の位置を 1 としてマークします (残りはすべてゼロです)。

次に、i をその値に設定します (i は while ループに使用する値です)。i が 2000000 未満の場合、マークされた配列にその特定の値のフラグを立てます。次に、i をその値だけインクリメントします。これは次のように行われます: 2 の倍数すべてにフラグを立てると、次の反復でそれらすべてを繰り返す必要がなくなります。たとえば。すべての 2 の倍数にフラグを立てる場合、次のステップでは、3^2 = 9 から 3 を開始できます。それまでに小さい倍数にはすべてフラグが立てられているためです。

詳細については、エラトステネスのふるいとこのビデオを参照してください。

于 2013-06-25T04:17:42.260 に答える
1

コードは基本的に素数を見つけるためにエラトステネスのふるいを使用していますが、合計を追跡するコードを取り出すと、より明確になる可能性があります。

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 に答える
0

この答えは、エラストテネスのふるいアプローチを使用して非素数をマークし（それがmarkedリストの目的です）、マークされていない値のみを追加します。詳細については、ウィキペディアの記事を参照してください。

于 2013-06-25T04:15:10.780 に答える