Drucken Sie alle einzigartige Kombination von Faktoren einer bestimmten Nummer

Question

Was ist der effizienteste Algorithmus zum Drucken aller einzigartigen Kombinationen von Faktoren einer positiven ganzen Zahl. Zum Beispiel, wenn die angegebene Nummer 24 dann sollte die Ausgabe

seine

24*1 
12*2 
8*3 
6*4 
6*2*2 
4*3*2 
3*2*2*2 

hier bemerken, dass, wenn 6 * 4 gedruckt wird dann 4 * 6 nicht gedruckt werden. Im Grunde ist es ein Problem, einzigartige Teilmengen zu nehmen, ohne die Reihenfolge zu berücksichtigen (eine Möglichkeit, das Problem zu betrachten). Das Ziel ist jedoch, eine Funktion zu haben, die am schnellsten läuft, sodass das Speichern der Faktoren in einer Datenstruktur für weitere Manipulationen mehr Zeit in Anspruch nehmen kann. Ich habe meinen Algorithmus ausprobiert und meinen Code unten eingefügt, aber es scheint mir nicht das gewünschte Ergebnis zu geben, ich mache einen Fehler in meinem rekursiven Aufruf. Können Sie mir helfen, einen effizienten Weg zu finden?

public static void printfact(int num){ 
     int temp=0; 
     for(int i=num-1;i>=num/2;i--){ 
      if(num % i == 0){ 
       temp = num/i; 
       System.out.println(temp + " * " + i); 
       if(isprime(i)==false){ 
        System.out.print(temp + " * "); 
        printfact(i); 
       } 
      } 
     } 
} 

Answer 1

1) Wenn i < num und i > num/2, dann num % i == num - i. (Einfach zu beweisen.) Ihre for-Schleife prüft sinnlos alle Ganzzahlen, die größer als num/2 sind, und die if-Anweisung wird nur einmal erfolgreich ausgeführt, mit temp == 2. Ich glaube nicht, dass du das wolltest.

2) In Ihnen behoben, dass die Rekursion muss möglicherweise eine Menge Antworten zu produzieren. Aber Sie drucken nur einmal temp *. Die Ausgabe wird also etwas seltsam aussehen.

3) isprime ist nicht erforderlich. num ist immer ein legitimer Faktor, ob es nun Prime ist oder nicht, vorausgesetzt, Sie folgen dem folgenden Punkt.

4) Schließlich müssen Sie herausfinden, wie Sie vermeiden, die gleiche Faktorisierung mehrmals auszudrucken. Die einfache Lösung besteht darin, nur Faktorisierungen zu erzeugen, bei denen die Faktoren monoton nicht ansteigen (wie in Ihrem Beispiel). Um dies zu tun, muss die Rekursion Faktorisierungen mit einem gewissen maximalen Faktor erzeugen (was der vorher entdeckte Faktor wäre). Also sollte die rekursive Funktion (mindestens) zwei Argumente haben: die Anzahl an Faktoren und den maximal erlaubten Faktor. (Sie müssen sich auch mit dem Problem befassen, das ich als Punkt 4 notiert habe.)

Der folgende Python-Code löst (glaube ich) das Problem, aber es tut immer noch ein paar unnötige Unterteilungen. In Abweichung vom Python-Stil druckt es jede Faktorisierung, anstatt als Generator zu fungieren, weil das einfacher in Java zu übersetzen ist.

# Uses the last value in accum as the maximum factor; a cleaner solution 
# would have been to pass max_factor as an argument. 
def factors(number, accum=[]): 
    if number == 1: 
    print '*'.join(map(str, accum)) 
    else: 
    if accum: 
     max_factor = min(accum[-1], number) 
    else: 
     max_factor = number 
    for trial_factor in range(max_factor, 1, -1): 
     remnant = number/trial_factor 
     if remnant * trial_factor == number: 
     factors(remnant, accum + [trial_factor,]) 

Es ist möglich, die for Anweisung zu optimieren. Zum Beispiel, sobald Sie remnant berechnen, wissen Sie, dass die nächste remnant mindestens eine größer sein muss, so dass Sie eine Reihe von trial_factor Werte überspringen können, wenn remnant klein ist.

Answer 2

Dieser Code alle Faktoren einer Zahl zu finden, sortieren sie (lokal und global):

public class PrimeFactors { 

    final SortedSet< List<Integer>> _solutions = new TreeSet<>(
     new Comparator<List<Integer>>(){ 
     @Override 
     public int compare(List<Integer> left, List<Integer> right) { 
      int count = Math.min(left.size(), right.size()); 
      for(int i = 0; i < count; ++i) { 
       if(left.get(i) < right.get(i)) { 
        return -1; 
       } 
       if(left.get(i) > right.get(i)) { 
        return +1; 
       } 
      } 
      return left.size() - right.size(); 
     }}); 

    public SortedSet< List<Integer>> getPrimes(int num) { 
     _solutions.clear(); 
     getPrimes(num, new LinkedList<Integer>()); 
     return _solutions; 
    } 

    private void getPrimes(int num, List<Integer> solution) { 
     for(int i = num - 1; i > 1; --i) { 
     if((num % i) == 0) { 
      int temp = num/i; 
      List<Integer> s = new LinkedList<>(); 
      s.addAll(solution); 
      s.add(temp); 
      s.add(i); 
      Collections.sort(s); 
      if(_solutions.add(s)) { // if not already found 
       s = new LinkedList<>(); 
       s.addAll(solution); 
       s.add(temp); 
       getPrimes(i, s); 
      } 
     } 
     } 
    } 
    public static void main(String[] args) { 
     SortedSet< List<Integer>> solutions = 
     new PrimeFactors().getPrimes(24); 
     System.out.println("Primes of 24 are:"); 
     for(List<Integer> l : solutions) { 
     System.out.println(l); 
     } 
    } 
} 

Ausgänge:

Primes of 24 are: 
[2, 2, 2, 3] 
[2, 2, 6] 
[2, 3, 4] 
[2, 12] 
[3, 8] 
[4, 6] 

Answer 3

diese rekursive Ansatz versuchen, die nämlich in zwei weitere Eingänge nimmt auch eine Zeichenkette, die den aktuellen Wert von i in for loop überträgt, um eine nachfolgende Verkleinerung durchzuführen, und ein temp int, um zu wissen, wann keine doppelten Umkehrungen gedruckt werden sollen, dh 8 * 3 und 3 * 8.

public static void printFactors(int number, String parentFactors, int parentVal) { 
    int newVal = parentVal; 
    for (int i = number - 1; i >= 2; i--) { 

     if (number % i == 0) { 
      if (newVal > i) { 
       newVal = i; 
      } 
      if (number/i <= parentVal && i <= parentVal 
        && number/i <= i) { 
       System.out.println(parentFactors + i + "*" + number/i); 
       newVal = number/i; 
      } 

      if (i <= parentVal) { 
       printFactors(number/i, parentFactors + i + "*", newVal); 
      } 
     } 

    } 

} 

Und rufen Sie diese Methode unter Verwendung von printFactors (12, '', 12)
Lassen Sie mich wissen, wenn Sie Fehler in diesem Ansatz finden. Vielen Dank!

Answer 4

vector<unsigned int> GetAllFactors(unsigned int number) 
{ 
    vector<unsigned int> factors; 

    for (int i = 2; i <= number; i++) 
    { 
     if (number % i == 0) 
     { 
      factors.push_back(i); 
     } 
    } 

    return factors; 
} 

void DoCombinationWithRepetitionFactors(vector<unsigned int> allFactors, unsigned currentProduct, unsigned targetProduct, vector<unsigned int> currentFactorSet, unsigned currentFactorIndex) 
{ 
    if (currentProduct == targetProduct) 
    { 
     for (auto a : currentFactorSet) 
     { 
      cout << a << " , "; 
     } 

     cout << endl; 

     return; 
    } 


    for (int i = currentFactorIndex; i < allFactors.size(); i++) 
    { 
     if (currentProduct * allFactors[i] <= targetProduct) 
     { 
      currentFactorSet.push_back(allFactors[i]); 
      DoCombinationWithRepetitionFactors(allFactors, currentProduct * allFactors[i], targetProduct, currentFactorSet, i); 
      currentFactorSet.pop_back(); 
     } 
    } 
} 

Answer 5

bool isprime(int n){ 
for(int i=2; i<=sqrt(n); i++) 
    if(n%i==0) 
     return false; 
return true; 
} 

void printprime(int n){ 

int i,j,y=n; 

while(y%2==0){ 
    cout<<"2 * "; 
    y/=2; 
} 

for(i=3; i<=sqrt(y); i+=2){ 
    while(y%i==0){ 
     cout<<i<<" * "; 
     y/=i; 
    } 
} 

if(y>2) 
    cout<<y; 
} 

void allfacs(int n){ 

int i; 
unordered_set<int> done; 

for(i=2; i<sqrt(n); i++){ 
    if(n%i==0){ 
     cout<<i<<" * "<<n/i<<endl; 

     if(!isprime(i) && done.find(i) == done.end()){ 
      done.insert(i); 
      printprime(i); 
      cout<<n/i<<endl; 
     } 
     if(!isprime(n/i) && done.find(n/i) == done.end()){ 
      done.insert(n/i); 
      cout<<i<< " * "; 
      printprime(n/i); 
      cout<<endl; 
     } 
    } 
} 
} 

Answer 6

Hier ist meine Lösung basiert auf Ideen des @ rici.

def factors(number, max_factor=sys.maxint): 
    result = [] 

    factor = min(number/2, max_factor) 
    while factor >= 2: 
     if number % factor == 0: 
      divisor = number/factor 

      if divisor <= factor and divisor <= max_factor: 
       result.append([factor, divisor]) 

      result.extend([factor] + item for item in factors(divisor, factor)) 

     factor -= 1 

    return result 

print factors(12) # -> [[6, 2], [4, 3], [3, 2, 2]] 
print factors(24) # -> [[12, 2], [8, 3], [6, 4], [6, 2, 2], [4, 3, 2], [3, 2, 2, 2]] 
print factors(157) # -> [] 

Answer 7

Ich habe eine Lösung ohne Rekursion oder Sortieren oder Stacks in C/C++.

#include <vector> 
#include <iostream> 

// For each n, for each i = n-1 to 2, try prod = prod*i, if prod < N. 

int 
g(int N, int n, int k) 
{ 
     int i = k; 
     int prod = n; 
     std::vector<int> myvec; 

     myvec.push_back(n); 
     while (i > 1) { 
       if (prod * i == N) { 
         prod = prod*i; 
         myvec.push_back(i); 
         for (auto it = myvec.begin(); 
           it != myvec.end(); it++) { 
           std::cout << *it << ","; 
         } 
         std::cout << std::endl; 
         return i; 
       } else if (prod * i < N) { 
         prod = prod*i; 
         myvec.push_back(i); 
       } else { i--;} 
     } 

     return k; 
} 

void 
f(int N) 
{ 
     for (int i = 2; i <= N/2; i++) { 
       int x = g(N, i, i-1); 
       // Extract all possible factors from this point 
       while (x > 0) { 
         x = g(N, i, x-1); 
       } 
     } 
} 

int 
main() 
{ 
     f(24); 

     return 0; 
} 

Und Ausgabe wie folgt lautet:

$ ./a.out 
    3,2,2,2, 
    4,3,2, 
    6,4, 
    6,2,2, 
    8,3, 
    12,2, 

Answer 8

ich mit diesem kam, scheint leicht zu lesen und zu verstehen. Ich hoffe es hilft!

def getFactors(num): 

    results = [] 

    if num == 1 or 0: 
     return [num] 

    for i in range(num/2, 1, -1): 

     if (num % i == 0): 
      divisor = num/i 

      if(divisor <= i): 
       results.append([i, divisor]) 

      innerResults = getFactors(divisor) 

      for innerResult in innerResults: 
       if innerResult[0] <= i: 
        results.append([i] + innerResult) 

    return results