Prime Factorization in Java

Question

Ich arbeite an einem Primfaktor-Faktorisierungsprogramm in Java, das alle Primfaktoren einer Zahl anzeigt, selbst wenn sie wiederholt werden. Und ich habe das:

public static void factors(int a) 
{ 
    int c=1; 
    for(int i = 1; i <= a;i++) 
    { 
     if(a%i == 0) 
     { 
      for(int k = 2; k < i; k++) 
      { 
       if(i%k == 0) 
       { 
        c = 1; 
        break; 
       } 
       else 
       { 
        c = 0; 
       } 
      } 
      if(c == 0 || i == 2) 
      { 
       System.out.print(i+ ", "); 
      } 
     } 
    } 
} 

Ich muss wiederholte Faktoren berücksichtigen (wie in 2, 2, 2 für 8). Wie könnte ich das ohne eine komplette Umstrukturierung tun?

Answer 1

Sie können eine andere Sammlung erstellen, die die Faktoren und ihre Anzahl verwaltet und schließlich wiederholte Faktoren berücksichtigen kann. Eine Karte mit Zählimpulsen wäre meine Wahl.

Answer 2

Ich denke, man anfangen sollte, und einen Algorithmus aus dieser einfachen Beschreibung bauen:

• Bereiten Sie eine List<Integer> von Primzahlen, die kleiner als oder gleich 2^16
• Run durch diese Liste aus niedrig bis hoch, jede Primzahl der Reihe nach als Kandidatendivisor versuchen
• Jedes Mal wenn Sie in einen Arbeitsdivisor laufen, teilen Sie es fortwährend aus, bis Sie die Zahl nicht mehr dadurch teilen können; dann weiter zur nächsten Primzahl
• Sobald Sie das Ende der Liste der Primzahlen erreicht haben, sollte Ihre verbleibende Nummer ebenfalls gedruckt werden, es sei denn, sie entspricht 1.

Das Finden einer Liste von Primzahlen ist ein Spaßproblem an sich. Dijkstra hat 1972 ein faszinierendes Kapitel darüber geschrieben. This article hat eine C++ - Implementierung und eine sehr nette Diskussion.

Answer 3

(1) if(c == 0 || i == 2) ist falsch, es wird auch 2 für a == 5 gedruckt.

(2) Um zu tun, was Sie fragen, ohne den Code (*) zu ändern, sollten Sie zählen, wie oft jeder Primfaktor durch die Zahl dividiert werden kann. Es kann einfach durchgeführt werden, indem eine neue Schleife, bevor der Druck Anweisung [Pseudo-Code] hinzufügen:

boolean b = true; 
int k = 1; 
while (b) { 
    if (a % (int) Math.pow(i, k+1) == 0) k++; 
    else b = false; 
} 

am Ende dieser Schleife bezeichnet k wie oft i ein Primfaktor von a ist.

(*) Hinweis: Obwohl dieser Ansatz funktionieren sollte, würde ich noch mit @KerrekSB Vorschlag zu einem Redesign gehen.