Generar todos los factores de un número dada su factorización prima

Question

Si ya tiene la factorización prima 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 pasar de 2 a sqrt (n) y encontrar todos los números divisibles, pero parece ineficiente porque ya tenemos la factorización prima.

Imagino que es básicamente una versión modificada de una función de combinaciones/elegir, pero todo lo que puedo encontrar son métodos para contar el número de combinaciones y maneras de contar el número de factores, no para generar realmente las combinaciones/factores.

Answer 1

Imagine los divisores principales son bolas en una cubeta. Si, por ejemplo, los divisores primos de su número son 2, 2, 2, 3 y 7, entonces puede tomar 0, 1, 2 o 3 instancias de 'bola 2'. Del mismo modo, puede tomar 'bola 3' 0 o 1 veces y 'bola 7' 0 o 1 vez.

Ahora, si toma 'ball 2' dos veces y 'ball 7' una vez, obtiene divisor 2 * 2 * 7 = 28. Del mismo modo, si no toma bolas, obtiene divisor 1 y si toma todas las bolas obtienes divisor 2 * 2 * 2 * 3 * 7 que equivale a numerarse.

Y, por último, para obtener todas las combinaciones posibles de bolas que puede sacar del cubo, puede usar fácilmente la recursión.

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, generando factores generalmente se considera una tarea muy difícil. De hecho, la protección de la mayoría de sus activos importantes (es decir, dinero, información, etc.) se basa en la tarea simple pero extremadamente difícil de factorizar un número. Consulte este artículo sobre el esquema de cifrado de RSA http://en.wikipedia.org/wiki/RSA_(cryptosystem). Estoy divagando.

Para responder a su pregunta, un enfoque combinatorio es su mejor método como lo señala Nikita (por cierto, felicitaciones por su explicación).

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

Muchas personas saltan a esta conclusión debido al concepto muy similar asociado con la generación de números primos. Desafortunadamente, esto es incorrecto, ya que omitirá varios factores mayores que el sqrt (n) que no son números primos (le dejaré probar esto a usted mismo).

Ahora, para determinar el número de factores para un número dado n, buscamos la factorización prima de n. Si n = p ^un, entonces sabemos que tendrá n (a + 1) factores (1, p, p , ..., p ^un). Esta es la clave para determinar el número total de factores.Si n tenían múltiples factores primos, por ejemplo

n = p ^{un middot}y; p ^b& middot; & middot; & middot; p _k^r

a continuación, utilizando la Regla Producto de recuento (http://en.wikipedia.org/wiki/Rule_of_product), sabemos que habrá

m = (a + 1) y middot; (b + 1) & middot; & middot; & middot; (r + 1)

factores. Ahora, todo lo que tenemos que hacer es encontrar todas las combinaciones posibles de los números que nos da la factorización prima. A continuación, hay algún código en R, que con suerte 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, lo primero que encuentro la descomposición en factores primos del número, digamos que tenemos,

n = p ^uny middot; p ^b& middot; & middot; & middot; p _k^r

entonces encuentro sólo los números primos singulares labled UniPrimes, por lo que para este ejemplo, UniPrimes contendría (p , p , p _k) Luego encuentro todos los poderes de cada primo y lo agrego a una matriz con la etiqueta MyFactors. Después de crear esta matriz, encuentro todas las posibles combinaciones de productos de los elementos en MyFactors. Por último, agrego 1 a la matriz (ya que es un factor trivial) y la clasifico. Voila! Es extremadamente rápido y funciona para números muy grandes con muchos factores.

He intentado hacer que el código sea lo más traducible posible a otros idiomas (es decir, supongo que ya ha creado una función que genera la factorización prima (o utiliza una función incorporada) y una función de prueba de número primo). y no utilicé funciones integradas especializadas únicas a R. Avíseme si algo no está claro. ¡Aclamaciones!

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