Génération de tous les facteurs d'un nombre donné son factorisation

Question

Si vous avez déjà la factorisation d'un nombre, ce qui est la meilleure façon d'obtenir l'ensemble de tous les facteurs de ce nombre? Je sais que je pouvais boucle de 2 à sqrt (n) et de trouver tous les nombres divisibles, mais cela semble inefficace puisque nous avons déjà le premier factorisation.

J'imagine qu'il est essentiellement une version modifiée d'une combinaison / choisir la fonction, mais tout ce que je peux sembler trouver est des méthodes pour compter le nombre de combinaisons et façons de compter le nombre de facteurs, de ne pas générer réellement les combinaisons / facteurs .

Answer 1

Imaginez les diviseurs premiers sont des boules dans un seau. Si, par exemple, les premiers de votre numéro diviseurs sont 2, 2, 2, 3 et 7, alors vous pouvez prendre 0, 1, 2 ou 3 cas de 'boule 2'. De même, vous pouvez prendre 'boule 3' 0 ou 1 fois et 'ball 7' 0 ou 1 fois.

Maintenant, si vous prenez « ballon 2 » deux fois et « ballon 7 » une fois, vous obtenez 2 * 2 diviseur * 7 = 28. De même, si vous prenez pas de balles, vous obtenez 1 et diviseur si vous prenez toutes les boules vous obtenir diviseur 2 * 2 * 2 * 3 * 7, qui correspond à au nombre lui-même.

Et enfin, pour obtenir toutes les combinaisons possibles de balles que vous pouvez prendre du seau, vous pouvez facilement utiliser récursivité.

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];
    }
}

Maintenant, vous pouvez l'exécuter sur exemple ci-dessus:

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

Answer 2

dimo414, générant des facteurs est généralement considéré comme une tâche très difficile. En fait, la protection de la plupart de vos actifs importants (à savoir l'argent, l'information., Etc.), reposent sur le simple, mais la tâche extrêmement difficile d'un certain nombre d'affacturage. Voir cet article sur le système de cryptage RSA http://en.wikipedia.org/wiki/RSA_ ( cryptosystème) . Je digresse.

Pour répondre à votre question, une approche combinatoire est votre meilleure méthode que sur pointé par Nikita (BTW, kudos sur votre explication).

  

Je sais que je pouvais boucle de 2 à sqrt (n) et trouver tous divisibles   numéros

Beaucoup de gens sautent à cette conclusion en raison du concept très similaire associé à des nombres premiers générateurs. Malheureusement, cela est inexact, car vous manquerez plusieurs facteurs supérieurs à la sqrt (n) qui ne sont pas des nombres premiers (je vous laisse le prouver à vous-même).

Maintenant, pour déterminer le nombre de facteurs pour un nombre donné n, nous regardons la factorisation de n . Si n = p ^a , alors nous savons que n aura ( a + 1 ) facteurs ( 1, p, p < sup> 2 , ..., p ^a ). Ceci est la clé pour déterminer le nombre total de facteurs. Si n avait plusieurs facteurs premiers, disons

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

puis en utilisant le Règle produit de comptage ( http: //en.wikipedia .org / wiki / Rule_of_product ), nous savons qu'il y aura

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

facteurs

. Maintenant, tout ce que nous devons faire est de trouver toutes les combinaisons possibles des chiffres qui nous sont donnés par la factorisation. Ci-dessous, est un code dans R, ce qui démontre, espérons-ce que je l'ai expliqué.

La première partie de mon code fait un simple contrôle de primalité, car si le nombre est premier, les seuls facteurs sont 1 et lui-même. Ensuite, si le nombre est pas premier et supérieur à 1, je trouve d'abord le premier factorisation du nombre, disons que nous avons,

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

Je trouve donc que les nombres premiers uniques labled UniPrimes, pour cet exemple, UniPrimes contiendrait ( p ₁ , p ₂ , p _k ). Je trouve donc tous les pouvoirs de chaque premier et l'ajouter à un tableau labled MyFactors. Après ce tableau est fait, je trouve toutes les combinaisons possibles de produit des éléments MyFactors. Enfin, ajouter 1 au tableau (comme il est un facteur trivial), et le tri. Le tour est joué! Il est extrêmement rapide et travaille pour un très grand nombre de nombreux facteurs.

J'ai essayé de rendre le code aussi traduisible que possible dans d'autres langues (c.-à-je suppose que vous avez déjà construit une fonction qui génère la factorisation (ou en utilisant une fonction intégrée) et une fonction de test des nombres premiers.) Et Je n'ai pas utilisé les fonctions intégrées uniques à R. Laissez-moi savoir si spécialisés sur quelque chose est pas clair. Vive!

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)
}