0

13195 の素因数は 5、7、13、29 です。600851475143 の最大の素因数は? @ http://projecteuler.net/problem=3

私は、プロジェクトのオイラー問題を解決できない場合は、見つけられる最善の解決策を理解するという取り決めがあります。私は、小さい数では機能するアルゴリズムを作成しましたが、大きな数では機能するには非効率的でした。だから私はザック・デントンの答えをグーグルで検索し、それを研究し始めました.

彼のコードは次のとおりです。

#!/usr/bin/env python
import math

def factorize(n):
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n+1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n+i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

print max(factorize(600851475143))

ここに私が自分で理解できないビットがあります：

  1. 2 番目の while ループで、なぜsqrt(n + 1)ただの代わりにa を使用するのsqrt(n)でしょうか。
  2. sqrt(n + 1)最初の while ループで偶数を反復処理するときに も使用しないのはなぜですか?
  3. アルゴリズムはどのようにして素因数のみを見つけることができますか? 私が最初に書いたアルゴリズムでは、因数が素数かどうかをチェックする別のテストがありましたが、彼は気にしませんでした。
4

1 に答える 1

2

  1. の不正確+1さに関係しているのでfloatはないかと思います（実際に必要なのか、それとも単に作者側の防御的な動きなのかはわかりません）。

  2. 最初のwhileループは からすべて 2 を因数分解しnます。sqrt(n + 1)そこにどのように収まるかわかりません。

  3. 小さな因子から大きな因子まで作業する場合、すべての複合候補が自動的に除外されます。考えてみてください: を因数分解すると、、など5は自動的に因数分解されます。それらが素数であるかどうかを確認する必要はありません。その時点で、 はそれらで割り切れなくなります。101520n

素数性のチェックが、元のアルゴリズムのパフォーマンスを低下させていると思われます。

于 2013-11-12T11:34:17.507 に答える