5

私はプロジェクトオイラー問題50に取り組んでいます。

素数41は、6つの連続する素数の合計として記述できます。

41 = 2 + 3 + 5 + 7 + 11 + 13これは、100未満の素数に追加される、連続する素数の最長の合計です。

1000未満の連続する素数の最長の合計で、素数に追加され、21の項が含まれ、953に等しくなります。

最も連続した素数の合計として、100万未満のどの素数を書くことができますか？

素数Pの項を決定するために（素数の合計として記述できる場合）、 Pまでの（ただし含まない）すべての素数のスライディングウィンドウを（昇順で）使用し、すべての合計を計算しますこれらのウィンドウ、合計が考慮される素数に等しい場合、ウィンドウの長さを数えます...

これは1000までのすべての素数で問題なく機能しますが、 10 ** 6までの素数では非常に遅いので、メモが役立つことを期待していました。スライディングウィンドウの合計を計算するとき、多くの二重の作業が行われます...（右？）

だから私はネット上で標準のメモの実装を見つけて、それを私のコードに貼り付けました、これは正しいですか？（ここでどのように機能するのかわかりません...）

primes = tuple(n for n in range(1, 10**6) if is_prime(n)==True)

count_best = 0


##http://docs.python.org/release/2.3.5/lib/itertools-example.html:
## Slightly modified (first for loop)
from itertools import islice
    def window(seq):
    for n in range(2, len(seq) + 1):

        it = iter(seq)
        result = tuple(islice(it, n))
        if len(result) == n:
            yield result    
        for elem in it:
            result = result[1:] + (elem,)
            yield result   

def memoize(function):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            val = function(*args)
            cache[args] = val
            return val
    return decorated_function


@memoize 


def find_lin_comb(prime):
    global count_best

    for windows in window(primes[0 : primes.index(prime)]):
        if sum(windows) == prime and len(windows) > count_best:
            count_best = len(windows)
            print('Prime: ', prime, 'Terms: ', count_best)


##Find them:
for x in primes[::-1]: find_lin_comb(x)

（ところで、素数のタプルは「きちんと」速く生成されます）

すべての入力に感謝します。私は単なる趣味のプログラマーなので、先に進まないでください。

ありがとうございました！

編集：これは、インデントを台無しにしない作業コードペーストです：http： //pastebin.com/R1NpMqgb

4

2 に答える 2

3

これは1000までのすべての素数で問題なく機能しますが、10 ** 6までの素数では非常に遅いので、メモが役立つことを期待していました。スライディングウィンドウの合計を計算するとき、多くの二重の作業が行われます...（右？）

はい、そうです。そしてもちろん、 106までの素数では遅いです。

nまでの素数がありN、昇順で番号が付けられているとしp_1 = 2, p_2 = 3, ...ます。素数かどうかを考えるとき。kは連続する素数の合計であり、。[p_i, ..., p_j]とのペアについては、すべてのウィンドウを考慮(i,j)しますi < j < k。それらが(k-1)*(k-2)/2あります。すべてkをn調べてn³/6、合計でウィンドウについて調べます（多重度を数えてw(i.j)、合計n-j時間で調べています）。ウィンドウを作成して合計するコストを無視しても、ウィンドウがどのように大きくスケーリングするかを確認できます。

  • についてN = 1000は、n = 168素数と約790000のウィンドウを調べる必要があります（多重度を数えます）。
  • についてN = 10**6は、n = 78498素数と8.3*10**13調べるウィンドウについてあります。

ここで、ウィンドウを作成して合計するための作業を考慮に入れ、で素数j-i+1を合計するためにそれを低く見積もると、の作業は約であり、合計作業はおおよそになります。ピーナッツの場合は3300万歩のようなものですが、ほぼ。j-i+1w(i,j)p_kk³/6k**4/24N = 10001.6*10**18N = 1000000

1年には約33.1*10**7秒が含まれ、CPUは約3 GHzで、約1017クロックサイクルです。つまり、100 CPU年のようなものを必要とする操作について話しているのです（10倍程度になる可能性があります）。

あなたはそんなに長く待つ気はないでしょう;）

これで、メモ化を使用すると、各ウィンドウを複数回確認できますが、各ウィンドウの計算は1回だけ実行します。つまりn³/6、ウィンドウの計算に必要な作業が必要でありn³/6、任意のウィンドウの時間を調べる必要があります。

  • 問題1：ウィンドウを数回見る必要があります8.3*10**13。1サイクルしか見ない場合でも、数時間かかります。
  • 問題2：メモ化する8.3*10**13ウィンドウについてあります。非常に大きなHDを使用できない限り、それほど多くのメモリはありません。

不要になったデータを破棄し、必要なときにのみウィンドウのデータを計算することで、メモリの問題を回避できますが、破棄する可能性のあるデータがわかれば、はるかに優れたアプローチを確認できるはずです。 。

1000未満の連続する素数の最長の合計で、素数に追加され、21の項が含まれ、953に等しくなります。

これは、その合計を生成するウィンドウについて何を教えてくれますか？どこから始めて、どこで止められますか？その情報をどのように使用して、問題を解決するための効率的なアルゴリズムを作成できますか？

于 2012-05-22T14:18:35.850 に答える
1

メモ化デコレータは、引数の各値（複数の引数の場合は値の各組み合わせ）の戻り値をキャッシュするラッパーを関数に追加します。同じ引数で関数が複数回呼び出される場合に便利です。純粋関数でのみ使用できます。

  1. この機能には副作用はありません。グローバル変数の変更と出力の実行は、副作用の例です。
  2. 戻り値は引数の値のみに依存し、呼び出し間で値を変更する可能性のある一部のグローバル変数には依存しません。

find_lin_comb関数が上記の基準を満たしていません。一つには、毎回異なる引数で呼び出され、もう一つには、関数は値を返しません。

于 2012-05-20T19:49:55.547 に答える