数値の最大の素因数を計算するための最良の方法は何ですか?
最も効率的だと思うのは次の通りです:
- きれいに割り切れる最小の素数を見つける
- 割り算の結果が素数かどうかをチェックする
- そうでない場合は次に低いものを探す
- 2に進みます。
この仮定は、小さな素因数を計算する方が簡単であるという前提に基づいています。これは正しいでしょうか? 他にどのようなアプローチを検討すべきでしょうか?
編集: 結果が他の 2 つの素数の積である場合にステップ 2 が失敗し、再帰アルゴリズムが必要になるため、2 つ以上の素因数が関係している場合は私のアプローチは無駄であることがわかりました。
再度編集: そして今、私はこれがまだ機能することに気付きました。なぜなら、最後に見つかった素数は最も大きい数である必要があるため、ステップ 2 の非素数の結果をそれ以上テストすると、より小さな素数になるからです。
ベストアンサー1
これは私が知っている最高のアルゴリズムです（Python）
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
上記の方法はO(n)、最悪の場合（入力が素数の場合）に実行されます。
編集：O(sqrt(n))以下は、コメントで提案されたバージョンです。 もう一度、コードを示します。
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d*d > n:
if n > 1: factors.append(n)
break
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list