0

完全数を検索することになっているこのプログラムがあります。(X を割るすべての数の合計を 2 で割った値が X に等しい場合、X は完全数です)
sum/2 = x

現在、古代ギリシャで知られていた最初の 4 つを発見したので、それほど素晴らしいものではありません。

次は 33550336 です。

これが大きな数であることはわかっていますが、プログラムは約 50 分間実行されていますが、まだ 33550336 が見つかりません。

プログラムの実行中にすべての完全数を格納する .txt ファイルを開いたためですか、それとも実行するのに十分な速度の PC を持っていないためですか*、または Python を使用しているからですか?

*注: この同じ PC は 10 分間で 500,000 を素因数分解しました (完全数プログラムと 3 つの YouTube タブを備えた Google Chrome も実行しています)。Python も使用しています。

プログラムのコードは次のとおりです。

i = 2
a = open("perfect.txt", 'w')
a.close()
while True:
    sum = 0
for x in range(1, i+1):
    if i%x == 0:
        sum += x
if sum / 2 == i:
    a = open("perfect.txt", 'a')
    a.write(str(i) + "\n")
    a.close()
i += 1
4

3 に答える 3

5

次は 33550336 です。

あなたのコード（原則としてあなたが望むようにインデントを修正しました）：

i = 2
a = open("perfect.txt", 'w')
a.close()
while True:
    sum = 0
    for x in range(1, i+1):
        if i%x == 0:
            sum += x
    if sum / 2 == i:
        a = open("perfect.txt", 'a')
        a.write(str(i) + "\n")
        a.close()
    i += 1

iの除数を求める除算を行いますi。

したがって、 までの完全数を見つけるにはn、

2 + 3 + 4 + ... + (n-1) + n = n*(n+1)/2 - 1

forループ内の分割。

さて、 に対してn = 33550336、それは

Prelude> 33550336 * (33550336 + 1) `quot` 2 - 1
562812539631615

おおよそ 5.6 * 10 14分割。

CPU が 1 秒あたり 10 9部門を実行できると仮定すると(そうではない可能性が高く、私の経験では 10 8がより適切な見積もりですがint、C のマシンの場合でも)、約 560,000 秒かかります。1 日は 86400 秒なので、およそ 6 日半 (10 8の見積もりで 2 か月以上) になります。

あなたのアルゴリズムは遅すぎて、妥当な時間内にそれに到達できません。

数論を使いたくない場合 (完全数でさえ非常に単純な構造を持ち、奇数の完全数が存在する場合、それらは必然的に巨大になります)、平方根までのみ分割することで、より良い結果を得ることができます。約数を見つけ、

i = 2
a = open("perfect.txt", 'w')
a.close()
while True:
    sum = 1
    root = int(i**0.5)
    for x in range(2, root+1):
        if i%x == 0:
            sum += x + i/x
    if i == root*root:
        sum -= x        # if i is a square, we have counted the square root twice
    if sum == i:
        a = open("perfect.txt", 'a')
        a.write(str(i) + "\n")
        a.close()
    i += 1

これは約 1.3 * 10 11の除数しか必要とせず、数時間で 5 番目の完全数を見つける必要があります。

完全数 (2^(p-1) * (2^p - 1)が素数pであるような素数の場合2^p - 1) の明示的な公式に頼ることなく、 の素因数分解を見つけて、そこiから除数の和を計算することで、いくらか高速化できます。これにより、すべての合成数のテストが高速になり、ほとんどの場合、はるかに高速になります。

def factorisation(n):
    facts = []
    multiplicity = 0
    while n%2 == 0:
        multiplicity += 1
        n = n // 2
    if multiplicity > 0:
        facts.append((2,multiplicity))
    d = 3
    while d*d <= n:
        if n % d == 0:
            multiplicity = 0
            while n % d == 0:
                multiplicity += 1
                n = n // d
            facts.append((d,multiplicity))
        d += 2
    if n > 1:
        facts.append((n,1))
    return facts

def divisorSum(n):
    f = factorisation(n)
    sum = 1
    for (p,e) in f:
        sum *= (p**(e+1) - 1)/(p-1)
    return sum

def isPerfect(n):
    return divisorSum(n) == 2*n

i = 2
count = 0
out = 10000
while count < 5:
    if isPerfect(i):
        print i
        count += 1
    if i == out:
        print "At",i
        out *= 5
    i += 1

私のマシンでは推定 40 分かかります。

悪くない見積もり:

$ time python fastperf.py 
6
28
496
8128
33550336

real    36m4.595s
user    36m2.001s
sys     0m0.453s
于 2013-04-27T22:05:47.140 に答える
0

なぜこれが起こったのかを推測することは非常に困難です。プログラムをデバッガーで実行し、コードが本当に正しいかどうかを手動で何度かテストすることをお勧めします (既に 4 つの数値を計算していることはわかっていますが、まだです)。あるいは、ロックなどで誤ってブロックされていないかどうかを確認するために、Python プロファイラーでプログラムを実行することをお勧めします。

于 2013-04-26T22:51:37.243 に答える
0

実行中にファイルを開くことに関連する問題である可能性はありますが、そうではありません。これが問題だった場合、エラー メッセージやプログラムの終了/クラッシュが発生した可能性があります。

プログラムを編集して、ログタイプの出力をファイルに頻繁に書き込みます。たとえば、100 万の偶数倍のターゲット番号を処理するたびに、日時、現在の番号、および最後の成功番号をログ ファイルに書き込みます (open-append-close)。

その後Type、時々ファイルを使用して進行状況を測定できます。

于 2013-04-26T23:16:56.570 に答える