Pythonで指定された最大のプライムファクタ

Question

私はこのサイト自体に出くわした次のコードブロックを理解できません。与えられた数の最大素因数を求める関数を作成します。それは以下の通りである：

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 

私の疑問機能prime_factors(n)がdがnの要因である場合は、whileループのみがチェックされているので、はnのなく素因数要因戻ってくるということで、もしそれがすべきであるような素数でもないならば。

私が間違っているのか、あなたのロジックの背後にある推論を指摘してください。さらに、私が正しいとすれば、適切なコードブロックとその背後にあるロジックを簡単に提供してください。コードをできるだけシンプルに保つようにしてください。

Answer 1

内側のループでは、nは、反復中にdで除算されることに注意してください。 nの新しい値が、それ以上dで割り切れるようにするための手段

while n % d == 0: 
    factors.append(d) 
    n /= d 

は、各反復の後に、それは不可能です。

例として、n = 3000としましょう。係数は素数ではない15です。しかし、nのでdが15に達した時点で、最初d = 3とd = 5によって渡され、nは3も5で割り切れるどちらの番号であったであろう、その非素因数15は今n % d == 0に合格しないだろう。

Answer 2

この関数は正しいですが、ブロック中には2番目の注意が必要です。与えられた数値をd変数で連続的に除算します。除算の結果が残っている場合は、このブロックを終了し、dを1つ増やしてから再び実行します。

これを念頭に置いて、この機能では、残りの数を2つに分けて、残りの数を除いた次の数に移動します。結局、結果には素数しか含まれません。それはこのように行くよ

：

def prime_factors(n): 
    factors = [] 
    d=2 
    while n > 1: 
    while n % d == 0: 
     factors.append(d) 
     n /= d 
    d += 1 
    return factors 

print(prime_factors(1000)) # will print [2, 2, 2, 5, 5, 5]