Erhalten der Primfaktorzerlegung einer Zahl schnell weniger als 100^100

Question

Ich möchte ein Programm machen, das die Primfaktorzerlegung von Zahlen der Größe 100^100 vergleichen kann. Ich möchte, dass das Programm mir sagt, ob es eine 2 gibt, zum Beispiel in der Primfaktorzerlegung, aber ich möchte nicht wissen, wie viele es gibt ... Und dann möchte ich die Primfaktorzerlegung zweier Zahlen vergleichen. Könnte jemand helfen? Die Schwierigkeit ist wirklich die Größe der Zahlen ... Und die Effizienz des Programms ... Ich möchte, dass der Vergleich zweier Zahlen dauert nur maximal 10 Sekunden ...

Ich habe dies;

import java.util.ArrayList; 
import java.util.List; 

public class PrimeFactorisation { 
    public static List<Integer> primeFactors(int numbers) { 
      int n = numbers; 
      List<Integer> factors = new ArrayList<Integer>(); 
      for (int i = 2; i <= n/i; i++) { 
        while (n % i == 0) { 
          factors.add(i); 
          n /= i; 
        } 
      } 
      if (n > 1) { 
        factors.add(n); 
      } 
      return factors; 
    } 

    public static void main(String[] args) { 
      System.out.println("Primefactors of 44"); 
      for (Integer integer : primeFactors(12345678901)) { 
        System.out.println(integer); 
      } 
    } 
} 

Dieser Code ist für Java, aber ich bin auf der Suche nach etwas primarly effizient, so bin ich bereit, die Sprache ... großen ganzen Zahlen

Answer 1

Im Allgemeinen werden Sie keine so großen Zahlen finden. Aber wenn Sie nur wissen wollen, ob zwei Zahlen mit Ausnahme der Multiplizität die gleichen Faktoren haben, ist das ziemlich einfach. Verwenden Sie den Euklid-Algorithmus, um den größten gemeinsamen Faktor der beiden Zahlen zu finden. Wenn das Ergebnis 1 ist, sind die Zahlen gleich und haben nicht die gleichen Faktoren. Andernfalls faktor den größten gemeinsamen Faktor in Primzahlen; das sollte viel einfacher sein, als die beiden großen Zahlen zu berücksichtigen, da es wahrscheinlich viel kleiner sein wird. Dann dividiere jede der großen Zahlen durch jeden der gemeinsamen Primfaktoren, bis sie sich nicht gleichmäßig teilt; Wenn nach der Division durch alle gemeinsamen Primfaktoren die beiden Reste gleich sind, können Sie deklarieren, dass die beiden ursprünglichen Zahlen die gleichen Primfaktoren haben, aber in unterschiedlichen Vielfachen, sonst wissen Sie, dass sie Primfaktoren haben, die nicht geteilt werden . Fragen Sie, ob Sie mehr wissen müssen.

Das ist eine ziemlich seltsame Anfrage. Was ist dein Anwendungsfall? Vielleicht gibt es eine andere Möglichkeit, das zugrunde liegende Problem zu lösen.

Answer 2

Diese sind zu ändern. Mit einer riesigen Integer-Bibliothek werden Sie die meisten von ihnen recht schnell auf ziemlich niedrige Werte reduzieren, indem Sie die niedrigen Faktoren ausrechnen, aber nicht alle - Primzahlen sind nicht ungewöhnlich.

Aber Sie brauchen die Faktoren nicht, Sie müssen wissen, ob zwei Zahlen einen gemeinsamen Faktor haben. Es gibt glaube ich einen Test dafür. Es ist ziemlich kompliziert und ein bisschen jenseits meiner mathematischen Erfahrung, aber es ist eine Komponente oder randomisierte Primalitätstests.