- Suponga que el número [math] N [/ math] en cuestión puede expresarse como [math] N [/ math] [math] = p \ times q [/ math]. Como [matemáticas] N [/ matemáticas] [matemáticas] <10 ^ {12}, [/ matemáticas] hay dos casos,
- [matemática] p <10 ^ {6} [/ matemática] y [matemática] q <10 ^ {6}, [/ matemática] [matemática] p [/ matemática] y [matemática] q [/ matemática] no necesariamente primos únicos, también pueden ser producto de primos.
- [matemática] p 10 ^ {6} [/ matemática] (viceversa para [matemática] p [/ matemática] y [matemática] q [/ matemática] )
Primero calculamos y almacenamos todos los números primos menores que [matemática] 10 ^ {6}. [/ Matemática] Esto se puede hacer fácilmente usando un Tamiz normal de Eratóstenes. Hay exactamente [math] 78498 [/ math] primos menores que [math] 10 ^ {6}. [/ Math] Calcule y almacénelos en una matriz.
Luego use estos números primos menos que [math] 10 ^ {6} [/ math] y factorice [math] N [/ math] [math]. [/ Math] El código se vería así, mientras está factorizando, puede almacenar los números primos y la potencia que divide [math] N. [/ math] C ++ sigue el código.
mapa caché;
para (auto p: primos) {
int cnt = 0;
while (N% p == 0) {
N / = p;
++ cnt;
}
si (cnt)
Caché [p] = cnt;
}
- En C #, ¿cómo podemos dividir un número BigInteger en otros dos números BigInteger?
- ¿Puedo obtener una breve descripción general del documento 'Generación precisa de hologramas utilizando el método basado en capas y el algoritmo de transformación de Fourier iterativo'?
- ¿Resolver problemas en Topcoder / Codeforces es una buena manera de aprender Java Collections Framework?
- ¿Cuáles son los algoritmos básicos en informática?
- Cómo contar el número de n rutas de borde que comienzan desde el nodo u en un DAG (gráfico acíclico dirigido)
Ahora, si todos los factores son todos menos que [matemática] N [/ matemática] entonces eso está bien y bueno, ¡factorizaste el número yay! En el caso de que al menos un primo sea [matemática]> 10 ^ {6}, [/ matemática] estás en problemas. Pero espera, ¿qué pasa con los dos supuestos que hicimos antes? Espera, vamos a cavar más profundo y ponerlos en uso.
Nos damos cuenta de que uno de los números primos es [matemática]> 10 ^ {6} [/ matemática]. Pero de la suposición 2, si uno de los factores es [matemática]> 10 ^ 6 [/ matemática], el otro tiene que ser [matemática] <10 ^ {6} [/ matemática] para respetar la condición de que [matemática] N 10 ^ {6} [/ math], una vez que eliminamos [math] N [/ math] de todos los primos menos que [math] 10 ^ {6} [/ math] y [math] N! = 1 [/ math] el número restante tendría que ser una conjetura, un primo.
Para hacer ese argumento más concreto, el número restante no puede ser un producto de 2 primos [matemática]> 10 ^ {6} [/ matemática] ya que eso haría que [matemática] N> 10 ^ {12}. [/ math] Entonces, solo sería un primo [math]> 10 ^ {6} [/ math]. Pon eso en la caché. Et Voila, tienes la factorización principal.
Todo esto se puede hacer en aproximadamente [matemáticas] \ Theta (n (\ log n) \ log (\ log n)) [/ matemáticas] donde [matemáticas] n = 10 ^ {6}. [/ math] La huella de memoria para esto sería [math] O (n) [/ math]. Este es el tiempo y la memoria necesarios para ejecutar un Tamiz de Eratóstenes normal en [matemáticas] n = 10 ^ {6} [/ matemáticas]. Y algo más de tiempo para factorizar, pero Big-Oh se encarga de todos modos.
