3 
p = []
for x in range(1, 50000000):
    count = 0
    for y in range(1, x // 2 + 1):
        if (x % y == 0):
            count += y
    if (count == x):
        p.append(x)

これは、1 から 50000000 の間で発生するすべての完全数を見つけようとする私のコードです。最初の 3 つの数字は正常に機能し、それらは 1 から 10000 の間です。しかし、進行するにつれて非常に遅くなります。10 秒ごとに 1000 個の数字を処理するようなものです。その後、最終的に 5 秒ごとに 10 個の数字を通過します。

とにかくこれをより速くすることができますか？x を 2 で割って、半分を超えないようにする (x の倍数にはならない) など、いくつかの小さなものを含めてみました。

4

3 に答える 3

2

あなたはもっとうまくやることができます。次の点を考慮してください。

1) 36 の因数分解を考えてみましょう: 1x36、2x18、3x12、4x9、6x6。以上です。さらに進んでも、新しいものは何も追加されません。次の因数分解は 9x4 ですが、それは既にわかっています (4x9)。この利点は次第に大きくなります (チェックする必要がある最後の数の根をその半分と比較してください)。

2) 奇数の完全数はありません。これは実際には推測ですが (まだ証明されていません)、10^300 未満のすべてを試しましたが、何も見つかりませんでした。したがって、50000000 未満のものは絶対にありません。つまり、用語の半分をスキップできます。

from math import ceil
p = []
for x in range(2, 50000000, 2):
    divisors = {1}
    for y in range(2, ceil(x**0.5) + 1):
        if x % y == 0:
            divisors.update({y, (x//y)})
    if sum(divisors) == x:
        print('-', x)
        p.append(x)
#- 6
#- 28
#- 496
#- 8128

これははるかに高速になるはずですが、できることは間違いなくもっとあります。

于 2016-11-16T10:56:28.090 に答える