複数の素因数を見つけるPython

Question

素因数を求めるコードを書く必要があります。また、私は複数回現れる要因を念頭に置く必要があります。 12のために、私は3と2

def prime_factors(n): 
for possible_prime in range(2,int(math.sqrt(n)+1)): 
    redundant=n%possible_prime 
    if redundant==0: 
     for last_check in range(2,int(math.sqrt(possible_prime)+1)): 
      redundant2=possible_prime%last_check 
      if redundant2!=0: 
       print(possible_prime) 

を返します。しかし、私は取得する必要があること2、2、3でコードを書く方法を知っている誰もが助けることはできますか？私はループとリストを使用することになっています。

ありがとうございます。あなたがループを最適化するためにrange()からすべての偶数を削除する必要があり、すべての

シャイ

Answer 1

まず、私はまた、一貫性のある型を保つためのsqrtの整数形式に1を加えることを示唆しています。 たびは可能総理は、このようにあなたが

def prime_factors(n): 
    factors = [] 
    for possible_prime in [2] + range(3, int(math.sqrt(n))+1, 2): 
     if not (n % possible_prime): 
      limit = int(math.sqrt(possible_prime) 
      is_prime = True 
      for factor in factors: 
       if factor > limit: 
        break 
       if not (possible_prime % factor): 
        is_prime = False 
        break 
      if is_prime: 
       factors.append(possible_prime) 
    return factors 

に対してチェックする必要がある数字の量を減らす、プライムまたはすでに見つかっプライマー要因の組み合わせのいずれか redundant == 0における第1のループの結果をあるように、第2のループは、いずれかの最適化されていません

あなたが言ったように、これはあなたにすべての素因数を与え、今私たちは複製（またはさらに）したいapropiate場合：

def prime_factors(n): 
    factors = [] 
    for possible_prime in [2] + range(3, int(math.sqrt(n))+1, 2): 
     if not (n % possible_prime): 
      limit = int(math.sqrt(possible_prime) 
      is_prime = True 
      for factor in factors: 
       if factor > limit: 
        break 
       if not (possible_prime % factor): 
        is_prime = False 
        break 
      if is_prime: 
       factors.append(possible_prime) 
    factors_copy = factors[:] 
    for factor in factors_copy: 
     i = 0 
     j = n 
     while not(j % factor): 
      i += 1 
      j /= factor 
     for k in range(i-1): 
      factors.append(factor) 
    return sorted(factors) 

Answer 2

私は、Pythonに新しいですが、それを試してみるだろう場合（私を修正してくださいシンセックスは完璧ではない）

def prime_factors(n): 
    prime_list = [] 
    job_done = False 
    first_prime = 2 
    while not job_done: 
     for possible_prime in range(first_prime,n+1): 
      if n%possible_prime == 0: 
       prime_list.append(possible_prime) 
       first_prime = possible_prime 
       n = int(n/possible_prime) 
       if n == 1: 
        job_done = True 
       break 
    return prime_list 

Answer 3

物事を単純で愚かなものにする方がよい場合があります（KISSの原則）。 素因数分解を実行するためのより効率的なアルゴリズムがあるが、この1つはストレートフォワードである：

import math 

def prime_factors(n): 
    res = [] 
    # handle factors 2 first 
    while n%2 == 0: 
     res.append(2) 
     n = n//2 
    fac = 3 
    # handle all odd factors until limit reached 
    while fac < int(math.sqrt(n))+1: 
     while n%fac == 0: 
      res.append(fac) 
      n = n//fac 
     fac += 2 
    # append remaining prime factor 
    if n > 2: 
     res.append(n) 
    return res 

print (prime_factors(2222222222)) 

パイソン3