La generación de todos los factores de un número dado su primer factorización

Question

Si ya tiene la descomposición en factores primos de un número, ¿cuál es la forma más fácil de obtener el conjunto de todos los factores de ese número? Sé que podría simplemente bucle de 2 a sqrt (n) y encontrar todos los números divisibles, pero que parece ineficiente puesto que ya tenemos la descomposición en factores primos.

Me imagino que es básicamente una versión modificada de un combinaciones / Realizar selección, pero todo lo que puedo encontrar es métodos para contar el número de combinaciones y formas de contar el número de factores, no para realmente generar las combinaciones / factores .

Answer 1

Imagínese divisores primos son bolas en un cubo. Si, por ejemplo, divisores primos de su número son 2, 2, 2, 3 y 7, entonces puede tomar 0, 1, 2 o 3 casos de 'bola 2'. Del mismo modo, se puede tomar 'bola de 3' 0 o 1 veces y 'bola 7' 0 o 1 veces.

Ahora, si se toma 'bola 2' dos veces y 'bola 7' una vez, se obtiene el divisor 2 * 2 * 7 = 28. Del mismo modo, si se toma ninguna bola, se obtiene el divisor 1 y si se toma todas las bolas que obtener divisor 2 * 2 * 2 * 3 * 7, que es igual al número en sí.

Y por último, para obtener todas las combinaciones posibles de las bolas que puede tomar desde el cubo, se podrían utilizar fácilmente la recursividad.

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

Ahora se puede ejecutar en el ejemplo anterior:

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

Answer 2

dimo414, los factores de la generación generalmente se considera una tarea muy difícil. De hecho, la protección de la mayor parte de sus activos importantes (es decir, dinero, información., Etc.), descansa en el sencillo pero extremadamente difícil tarea de factorizar un número. Ver este artículo sobre el sistema de cifrado RSA http://en.wikipedia.org/wiki/RSA_ ( criptosistema) . I paréntesis.

Para responder a su pregunta, un enfoque combinatorio es su mejor método cabo en punta Nikita (por cierto, felicitaciones en su explicación).

  

Sé que podría simplemente bucle de 2 a sqrt (n) y encontrar todos los divisibles   números

Muchas personas saltar a esta conclusión debido al concepto muy similar asociado con la generación de números primos. Por desgracia, esto es incorrecto, ya que se perderá varios factores mayores que el sqrt (n) que no son números primos (te dejaré probar esto a ti mismo).

Ahora, para determinar el número de factores para cualquier número dado n, esperamos que la factorización prima de n . Si n = p ^a , entonces sabemos que n tendrá ( a + 1 ) factores ( 1, p, p < sup> 2 , ..., p ^a ). Esta es la clave para determinar el número total de factores. Si n había varios factores primos, por ejemplo

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

presionando el regla del producto de conteo ( http: //en.wikipedia .org / wiki / Rule_of_product ), sabemos que habrá

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

factores. Ahora, todo lo que necesita hacer es encontrar todas las combinaciones posibles de los números dados a nosotros por la descomposición en factores primos. A continuación, hay un código en R, que es de esperar demuestra lo que he explicado.

La primera parte de mi código hace una simple comprobación de primalidad porque si el número es primo, los únicos factores son 1 y sí mismo. A continuación, si el número no es primo y mayor que 1, en primer lugar encontrar la factorización prima del número, digamos que tenemos,

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

luego encontrar sólo los números primos singulares labled UniPrimes, por lo que para este ejemplo, UniPrimes contendría ( p ₁ , p ₂ , p _k ). entonces encuentro todos los poderes de cada primer y añadirlo a una serie labled MyFactors. Una vez realizada esta matriz, encuentro todas las combinaciones posibles de productos de los elementos en MyFactors. Por último, añado 1 a la matriz (ya que es un factor trivial), y ordenarla. Voila! Es extremadamente rápido y funciona para un número muy grande con muchos factores.

he intentado hacer el código como traducible como sea posible a otros idiomas (es decir, que se supone que ya ha construido una función que genera la descomposición en factores primos (o utilizando una función incorporada) y una función de prueba número primo.) Y yo no uso especializado incorporado funciones únicas a R. Déjeme saber si algo no está claro. Saludos!

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