Faktorisieren einer Ganzzahl in einer Liste von ganzen Zahlen

Question

Ich versuche, ein Skript zu schreiben, das bestimmt, ob es möglich ist, einen ganzzahligen Wert in einer Liste von Ganzzahlen zu faktorisieren. Die Art und Weise, wie ich es gemacht habe, ist rekursiv nach einer gültigen Faktorisierung zu suchen, effektiv ein DFS in einem Baum von möglichen Faktoren zu machen (in dem Code unten). Ist es möglich, einen gierigen Algorithmus zu entwickeln, der das schnell findet? Meine Idee war, die Liste nach dem größten Faktor im Rest zu durchsuchen, bis eine gültige Faktorisierung gefunden wurde. Wird das in diesem Fall ein richtiger Algorithmus sein? Wenn nicht, ist dieses Problem in NP?

Code, um das Problem in Python geschrieben zu lösen:

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 

EDIT: Zum Beispiel gegebene ganze Zahl 30 und Liste [2,3,5,8], sollte der Algorithmus return true, weil 30 = 2 * 3 * 5. Es ist nicht erforderlich, alle Elemente in der Liste zu verwenden, da Faktoren und Faktoren mehr als einmal verwendet werden können.

Answer 1

Es ist keine Tiefensuche erforderlich, und das Problem ist linear in der Größe der Liste der möglichen Faktoren. Hier ist eine Funktion, die entweder die Faktorisierung der Zielnummer zurückgibt, oder falsch, wenn sie nicht über die Liste von Faktoren berücksichtigt werden können:

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 

ich die Funktion smooth genannt, weil, dass das Konzept in der Zahlentheorie ist, dass Sie versuchen, zu berechnen: eine Zahl, die Faktoren über eine gegebene Liste ist glatt über diese Liste von Faktoren. Für die meisten Anwendungen möchten Sie wahrscheinlich, dass alle möglichen Faktoren prim sind.