Generazione di tutti i fattori di un numero data la sua fattorizzazione in numeri primi

Question

Se hai già la fattorizzazione primo di una serie, qual è il modo più semplice per ottenere l'insieme di tutti i fattori di quel numero? So che ho potuto solo anello da 2 a sqrt (n) e trovare tutti i numeri divisibili, ma che sembra inefficiente poiché abbiamo già la fattorizzazione prima.

Immagino che è sostanzialmente una versione modificata di un combinazioni / scegliere la funzione, ma tutto quello che riesco a trovare è metodi per contare il numero di combinazioni, e modi di contare il numero di fattori, non realmente generare le combinazioni / fattori .

Answer 1

Immaginate primi divisori sono palle in un secchio. Se, ad esempio, divisori primi del vostro numero sono 2, 2, 2, 3 e 7, allora si può prendere 0, 1, 2 o 3 casi di 'pallone 2'. Allo stesso modo, si può prendere 'palla 3' 0 o 1 volta e 'palla 7' 0 o 1 volta.

Ora, se si prende 'pallone 2' due volte e 'palla 7', una volta, si ottiene divisore 2 * 2 * 7 = 28. Allo stesso modo, se si prende senza palle, si ottiene divisore 1 e se si prende tutte le palle voi ottenere divisore 2 * 2 * 2 * 3 * 7 che equivale al numero stesso.

E alla fine, per ottenere tutte le possibili combinazioni di palle si può prendere dal secchio, si potrebbe facilmente utilizzare la ricorsione.

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

Ora è possibile eseguirlo su esempio di cui sopra:

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

Answer 2

dimo414, generando fattori è generalmente considerato un compito molto difficile. In effetti, la protezione della maggior parte dei vostri beni importanti (vale a dire il denaro, informazioni., Ecc), riposare sulla semplice, ma estremamente difficile compito di factoring un numero. Si veda questo articolo sul sistema di crittografia RSA http://en.wikipedia.org/wiki/RSA_ ( crittografico) . Sto divagando.

Per rispondere alla tua domanda, un approccio combinatorio è il vostro metodo migliore come fuori punte da Nikita (a proposito, complimenti per aver spiegazione).

  

So che potrei solo anello da 2 a sqrt (n) e trovare tutti divisibili   Numeri

Molte persone saltare a questa conclusione a causa del concetto molto simile associati con i numeri primi che generano. Purtroppo, questo non è corretto, in quanto vi perderete diversi fattori superiori al sqrt (n) che non sono numeri primi (ti farò provare questo a te stesso).

Ora, per determinare il numero di fattori per un dato numero n, si guarda al fattorizzazione prima di n . Se n = p ^a , quindi sappiamo che n avrà ( a + 1 ) fattori ( 1, p, p < sup> 2 , ..., p ^a ). Questa è la chiave per determinare il numero totale di fattori. Se n era molteplici fattori primi, diciamo

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

quindi utilizzando il del prodotto regola di conteggio ( http: //en.wikipedia .org / wiki / Rule_of_product ), sappiamo che ci saranno

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

fattori. Ora, tutto quello che dobbiamo fare è trovare ogni possibile combinazione di numeri dati comunicati dalla fattorizzazione prima. Di seguito, è un codice in R, si spera che dimostra ciò che ho spiegato.

La prima parte del mio codice fa un semplice controllo di primalità perché se il numero è primo, gli unici fattori sono 1 e per sé. Poi, se il numero non è primo e maggiore di 1, in primo luogo ho trovato la fattorizzazione prima del numero, dire che abbiamo,

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

Poi ho trovato solo i numeri primi uniche etichettati UniPrimes, così per questo esempio, UniPrimes conterrebbe ( p ₁ , p ₂ , p _k ). Poi ho trovato tutti i poteri di ogni primo e aggiungerlo a una serie etichettati MyFactors. Dopo questo array è fatto, trovo ogni possibile combinazione prodotto degli elementi in MyFactors. Infine, aggiungo 1 alla matrice (in quanto è un fattore banale), e di risolvere. Ecco! E 'estremamente veloce e lavora per numeri molto grandi con molti fattori.

Ho cercato di rendere il codice come traducibile possibile per altre lingue (cioè io per scontato che avete già costruito una funzione che genera la fattorizzazione primo (o utilizzando un built-in funzione) e di una funzione di test numero primo.) E non ho usato specializzati built-in funzioni uniche a R. fatemi sapere se qualcosa non è chiaro. 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)
}