Erzeugen aller Faktoren einer Zahl angesichts der Primfaktorzerlegung

Question

Wenn Sie bereits die Primfaktorzerlegung einer Zahl haben, was ist der einfachste Weg, um die Menge aller Faktoren dieser Zahl zu bekommen? Ich weiß, ich könnte nur Schleife von 2 bis sqrt (n) und alle teilbaren Zahlen finden, aber das scheint ineffizient, da wir bereits die Primfaktorzerlegung haben.

Ich stelle ich vor, es ist im Grunde eine modifizierte Version einer Kombination / wähle Funktion, aber alles, was ich scheinen kann, sind, Methoden zu finden, um die Anzahl von Kombinationen zu zählen, und Möglichkeiten, die Anzahl von Faktoren zählen, nicht um tatsächlich die Kombinationen / Faktoren zu erzeugen .

Answer 1

Stellen Sie sich vor Primteilern sind Bälle in einen Eimer. Wenn zum Beispiel Primteilern Ihre Nummer 2, 2, 2, 3 und 7, dann kann man 0 nehmen, 1, 2 oder 3 Instanzen von 'Ball 2'. Ebenso können Sie nehmen 'Ball 3' 0 oder 1 mal und 'Kugel 7' 0 oder 1 mal.

Nun, wenn Sie nehmen ‚Ball 2‘ zweimal und ‚Ball 7‘ einmal, erhalten Sie Divisor 2 * 2 * 7 = 28. Und falls Sie keine Kugeln nehmen, Sie Divisor 1 erhalten, und wenn Sie nehmen alle Kugeln Sie erhalten Divisor 2 * 2 * 2 * 3 * 7, die sich auf die Anzahl entspricht.

Und endlich bekommt alle möglichen Kombinationen von Kugeln, die Sie aus dem Eimer nehmen, können Sie leicht Rekursion verwenden könnten.

void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) {
    if (currentDivisor == primeDivisors.length) {
        // no more balls
        System.out.println(currentResult);
        return;
    }
    // how many times will we take current divisor?
    // we have to try all options
    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
        findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult);
        currentResult *= primeDivisors[currentDivisor];
    }
}

Jetzt können Sie es auf obiges Beispiel ausgeführt:

findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);

Answer 2

dimo414, Faktoren zu erzeugen ist in der Regel eine sehr schwierige Aufgabe betrachtet. In der Tat, der Schutz der meisten wichtigen Vermögenswerte (das heißt Geld, info., Etc.), ruht auf dem einfachen, aber äußerst schwierige Aufgabe, eine Reihe von Factoring. Lesen Sie diesen Artikel auf dem RSA-Verschlüsselungsschema http://en.wikipedia.org/wiki/RSA_ ( Kryptosystem) . Ich schweife ab.

Um Ihre Frage zu beantworten, ein kombinatorischer Ansatz ist die beste Methode Wie von Nikita (btw, einem dicken Lob auf Ihrer Erklärung).

  

Ich weiß, ich könnte nur Schleife von 2 bis sqrt (n) und alle teilbar finden   Zahlen

Viele Menschen zu diesem Schluss springen wegen des sehr ähnlichen Konzepts mit der Erzeugung von Primzahlen verbunden. Leider ist dies nicht korrekt, wie Sie verschiedene Faktoren größer als die sqrt (n) verpassen, die nicht Primzahlen sind (ich lasse Sie dies selbst nachprüfen).

Nun, die Anzahl der Faktoren für eine gegebene Zahl n, um zu bestimmen, schauen wir auf die Primfaktorzerlegung von n . Wenn n = p ^a , dann wissen wir, dass n haben ( a + 1 ) Faktoren ( 1, p, p < sup> 2 , ..., p ^a ). Dies ist der Schlüssel um die Gesamtzahl von Faktoren zu bestimmen. Wenn n hatte mehrere Primfaktoren, sagen wir

n = p ₁ ^a · p ₂ ^b ··· p _k ^r

dann mit der Produktregel des Zählens ( http: //en.wikipedia .org / wiki / Rule_of_product ), wir wissen, dass es sein

m = ( a + 1 ) · ( b + 1 ) ··· ( r + 1 )

Faktoren. Nun, alles, was wir tun müssen, ist jede mögliche Kombination der Zahlen, die von der Primfaktorzerlegung gegeben finden. Unten ist ein Code in R, die hoffentlich zeigt, was ich erklärt habe.

Der erste Teil meiner Code macht eine einfache Prüfung von primality denn wenn die Zahl eine Primzahl ist, sind die einzigen Faktoren sind 1 und sich selbst. Als nächstes, wenn die Zahl keine Primzahl ist und größer als 1 ist, habe ich zunächst die Primfaktorzerlegung der Zahl finden, sagen wir,

n = p ₁ ^a · p ₂ ^b ··· p _k ^r

ich dann nur die eindeutigen Primzahlen labled finden UniPrimes, so für dieses Beispiel würde UniPrimes enthalten ( p ₁ , p ₂ , p _k ). Ich finde dann alle Kräfte jedes prime und fügen Sie ihn in einem Array labled MyFactors. Nach dieser Anordnung hergestellt ist, ich alle möglichen Produktkombination der Elemente in MyFactors finden. Schließlich fügen I 1 zu dem Feld (wie es ein trivialer Faktor ist), und es sortieren. Voila! Es ist extrem schnell und arbeitet für sehr große Zahlen mit vielen Faktoren ab.

Ich habe versucht, den Code als übersetzbar wie möglich in andere Sprachen zu machen (dh Ich gehe davon aus, dass Sie bereits eine Funktion aufgebaut haben, die die Primfaktorzerlegung (oder über eine eingebaute Funktion) und eine Primzahl Testfunktion erzeugt.) Und ich habe nicht spezialisierte integrierte Funktionen nutzen einzigartig R. Lassen Sie mich wissen, wenn etwas nicht klar ist. Cheers!

factor2 <- function(MyN) {

    CheckPrime <- isPrime(MyN)

    if (CheckPrime == F && !(MyN == 1)) {
            MyPrimes <- primeFactors(MyN)
            MyFactors <- vector()
            MyPowers <- vector()
            UniPrimes <- unique(MyPrimes)
                    for (i in 1:length(UniPrimes)) {

                            TempSize <- length(which(MyPrimes == UniPrimes[i]))

                            for (j in 1:TempSize) {
                                    temp <- UniPrimes[i]^j
                                    MyPowers <- c(MyPowers, temp)
                            }

                    }
            MyFactors <- c(MyFactors, MyPowers)
            MyTemp <- MyPowers
            MyTemp2 <- vector()
            r <- 2
            while (r <= length(UniPrimes)) {

                    i <- 1L

                    while (i <= length(MyTemp)) {
                            a <- which(MyPrimes >  max(primeFactors(MyTemp[i])))
                                    for (j in a) {
                                            temp <- MyTemp[i]*MyPowers[j]
                                            MyFactors <- c(MyFactors, temp)
                                            MyTemp2 <- c(MyTemp2, temp)
                                    }
                            i <- i + 1
                    }
                    MyTemp <- MyTemp2
                    MyTemp2 <- vector()
                    r <- r + 1
            }
    } else {
            if (MyN == 1) {
                    MyFactors <- vector()
            } else {
                    MyFactors <- MyN
            }
    }
    MyFactors <- c(1, MyFactors)
    sort(MyFactors)
}