java - primos - factorizacion de numeros compuestos
Generando todos los factores de un número dada su factorización prima. (2)
Imagina que los divisores principales son bolas en un cubo. Si, por ejemplo, los divisores principales de su número son 2, 2, 2, 3 y 7, entonces puede tomar 0, 1, 2 o 3 instancias de ''ball 2''. Del mismo modo, puede tomar ''ball 3'' 0 o 1 veces y ''ball 7'' 0 o 1 veces.
Ahora, si tomas ''ball 2'' dos veces y ''ball 7'' una vez, obtienes el divisor 2 * 2 * 7 = 28. Similarmente, si no tomas bolas, obtienes el divisor 1 y si tomas todas las bolas obtienes el divisor 2 * 2 * 2 * 3 * 7 que es igual al número en sí.
Y por último, para obtener todas las combinaciones posibles de bolas que puedes sacar del cubo, puedes usar la recursión fácilmente.
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 puedes ejecutarlo en el ejemplo anterior:
findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);
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 pasar de 2 a sqrt (n) y encontrar todos los números divisibles, pero eso parece ineficiente ya que ya tenemos la factorización prima.
Me imagino que es básicamente una versión modificada de una función de combinación / elecció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 generar combinaciones / factores.
dimo414, los factores generadores generalmente se consideran 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 en el esquema de cifrado 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 en su explicación).
Sé que podría pasar 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 perderá varios factores mayores que el sqrt (n) que no son números primos (le dejaré que se lo demuestre).
Ahora, para determinar el número de factores para cualquier número dado n, observamos la factorización prima de n . Si n = p a , entonces sabemos que n tendrá factores (a + 1 ) ( 1, p, p 2 , ..., p a ). Esta es la clave para determinar el número total de factores. Si n tenía múltiples factores primos, diga
n = p 1 a · p 2 b ··· p k r
luego, utilizando la Regla de conteo del producto ( http://en.wikipedia.org/wiki/Rule_of_product ), sabemos que habrá
m = ( a + 1 ) · ( b + 1 ) ··· ( r + 1 )
Factores Ahora, todo lo que tenemos que hacer es encontrar todas las combinaciones posibles de los números que nos proporciona la factorización prima. A continuación, hay un 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 es mayor que 1, primero encuentro la factorización prima del número, digamos que tenemos
n = p 1 a · p 2 b ··· p k r
Luego, solo encuentro los números primos únicos etiquetados como UniPrimes, por lo que para este ejemplo, UniPrimes contendría ( p 1 , p 2 , p k ). Luego encuentro todos los poderes de cada primo y lo agrego a una matriz etiquetada como MyFactors. Después de realizar esta matriz, encuentro todas las combinaciones posibles de productos de los elementos en MyFactors. Por último, agrego 1 a la matriz (ya que es un factor trivial) y lo clasifico. Voila! Es extremadamente rápido y funciona para números muy grandes con muchos factores.
Traté de 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 usando una función incorporada) y una función de prueba de números primos) y no lo hice. t usa funciones integradas especializadas exclusivas de R. Déjame saber 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)
}