5

13195の素因数は5、7、13、29です。数600851475143の最大の素因数は何ですか？

私はProjectEulerでこの問題を自分のやり方で解決しましたが、それは遅かったのですが、誰かのgithubアカウントでこの解決策を見つけました。なぜそれが機能するのか理解できません。インデックスに等しい多くの要因が削除されるのはなぜですか？何か洞察はありますか？

def Euler3(n=600851475143):
    for i in range(2,100000):
        while n % i == 0:
            n //= i
            if n == 1 or n == i:
                return i
4

3 に答える 3

8

この関数は、入力の連続する要素を見つけることによって機能します。それが見つける最初の要因は必然的に素数になります。素因数が見つかった後、それは元の数から除算され、プロセスが続行されます。それらをすべて分割するまでに（1、または現在の係数（i）を残す）、最後の（最大の）ものが得られます。

ここにトレースコードを追加しましょう：

def Euler3(n=600851475143):
    for i in range(2,100000):
        while n % i == 0:
            n //= i
            print("Yay, %d is a factor, now we should test %d" % (i, n))
            if n == 1 or n == i:
                return i

Euler3()

これの出力は次のとおりです。

$ python factor.py
Yay, 71 is a factor, now we should test 8462696833
Yay, 839 is a factor, now we should test 10086647
Yay, 1471 is a factor, now we should test 6857
Yay, 6857 is a factor, now we should test 1

確かに、一般的な解決策では、範囲の上限はnの平方根であるはずですが、Pythonの場合、呼び出しmath.sqrtは浮動小数点数を返すため、元のプログラマーは怠惰なショートカットを使用していたと思います。このソリューションは一般的には機能しませんが、オイラープロジェクトには十分でした。

しかし、アルゴリズムの残りの部分は健全です。

于 2012-09-26T15:55:33.417 に答える
3

n=20の場合の解決方法を検討してください。

iteration i=2
  while true (20 % 2 == 0)
    n = n//2 = 20//2 = 10
    if (n == 1 or n == 2) false
  while true (10 % 2 == 0)
    n = n//2 = 10//2 = 5
    if (n == 1 or n == 2) false
  while false (5 % 2 == 0)
iteration i = 3
  while false (5 % 3 == 0)
iteration i = 4 
  while false (5 % 4 == 0)
iteration i = 5
  while true (5 % 5 == 0)
    n = n//5 = 5//5 = 1
    if (n == 1 or n == 5) true
      return i, which is 5, which is the largest prime factor of 20

これは単に因子を削除するだけであり、すでに複数の素因数（whileループ）を削除しているため、iの多くの値は実際には無駄な労力です。ループ内で何かを行う可能性があるiの唯一の値は、iのプライム値です。n == iテストは、素数の2乗である25のような数の場合をカバーします。ただし、範囲は限られているようです。2 *（100,000の次に大きい素数）の正解は得られません。

于 2012-09-26T15:59:18.333 に答える
1

誰もあなたの質問に実際に答えていません。forループは各番号を順番にテストしiます。が係数のwhile場合、ループのテストは成功します。その場合は、を減らし、またはと比較して終了したかどうかを確認します。テストは、複数回分割する場合の（だけでなく）です。inni1nwhileifin

賢いですが、それは試行除算による整数因数分解が通常書かれている方法ではありません。n係数が100000を超える場合も機能しません。ブログに説明があります。これが私のバージョンの関数でn、最大のものだけでなく、のすべての要素がリストされています。

def factors(n):
    fs = []
    while n % 2 == 0:
        fs += [2]
        n /= 2
    if n == 1:
        return fs
    f = 3
    while f * f <= n:
        if n % f == 0:
            fs += [f]
            n /= f
        else:
            f += 2
    return fs + [n]

この関数は個別に処理し、奇数の要素2のみを試行します。また、因子に制限を設けるのではなく、因子が残りの平方根よりも大きいときに停止します。これは、その時点で素数でなければならないためです。因子は昇順で挿入されるため、出力リストの最後の因子が最大になります。これは、必要な因子です。nn

于 2012-09-26T17:41:56.907 に答える