整数リストの整数を因数分解する

Question

私は、整数リストの整数値を因数分解できるかどうかを判断するスクリプトを作成しようとしています。私がやったやり方は、有効な因子分解のためにrecursivleyを検索することです。有効な要素のツリー内でDFSを実行します（下記のコードを参照）。これは速く見つける貪欲なアルゴリズムを作ることは可能ですか？私の考えは、有効な因数分解が見つかるまで、残りの部分で最大の要素を探し続けることでした。この場合正しいアルゴリズムでしょうか？もしそうでなければ、NPでこの問題はありますか？

Pythonで書かれた問題解決するためにコード：EDIT

def can_factorize_in_list(n, list): 
    # Determines whether it is possible to factorize 'n' in 'list' 
    # Filter the list to only include the values which are factors 
    fac_list = [p for p in list if (n % p is 0)] 
    for x in fac_list: 
     if n % x is 0: 
      if n/x is 1: 
       # If we end up at 1, we have a valid factorization 
       return 1 # End state 
      else: 
       # If we do not end at 1, keep trying 
       if can_factorize_in_list(n/x, fac_list): 
        return 1 
       else: 
        continue 
    return 0 

を：例えば、指定された整数30とリスト30 = 2ため、[2,3,5,8]、アルゴリズムがtrueを返します* 3 * 5。因子と因子を複数回使用できるので、リストのすべての要素を使用する必要はありません。

Answer 1

潜在的な要因のリストのサイズの問題は、深さ優先検索の必要はなく、問題は線形です。ここではそれが要因のリスト上で因数分解できない場合、目標数の因数分解を返す、またはFalseという機能があります：

def smooth(n, fs): 
    xs = [] 
    for f in fs: 
     if n == 1: return xs 
     while n % f == 0: 
      n = n/f 
      xs.append(f) 
    if n == 1: return xs 
    return False 

それはあなたがしようとしていることを数論における概念ですので、私は機能smoothと呼ばれます計算する：与えられたリストを要因とする数は、その要素のリスト上で平滑と言われています。ほとんどのアプリケーションでは、すべての潜在的な要因をプライムにすることをお勧めします。