Factorizando números.

Buenas.
Igual que muchos de los escritores tiempo sin pasar por aca por las ocupaciones pero bien intentando retomar el blog.

Veamos los factores primos de un número son los primos divisores exactos de este por ejemplo

algún otro ejemplo


ok sabiendo esto vamos a buscar los números primos, podemos hacerlo si bien por cada número ir comprobando la divisibilidad por cada número lo que haremos es usar un algoritmo mucho más eficiente para esto, usaremos una criba de eratostenes.

La criba es un algoritmo bastante fácil de implementar, la cual consiste en ir tachando números no primos, veamos un ejemplo de como funciona lo describe esta imagen:

dar click sobre la imagen para ver la animacion

Y su implementación en C++ sería algo como

bool primes[primes_size + 1];

memset (primes, 0x1, sizeof primes);

for (size_t p = 2; p <= primes_size; ++p) {
	if (primes[p])
		for (size_t i = p * 2; i <= primes_size; i += p)
			primes[i] = false;
}

ok ya tenemos guardados los números primos o más bien en la posición donde se marque el nos dira si es primo o no lo que podemos hacer es ir comprobando para crear un vector de números primos como tal y luego buscar los factores.

Supongamos que se hizo tal cosa y tenemos un arreglo llamado “nprimes” cargado con los números primos y el número a factorizar sea un k, la factorización sería algo como esto:

ptr = &nprimes[0];

vector<int> factors;

while (k > 1 && *ptr && *ptr * *ptr <= k) {
         while (k % *ptr == 0 && k > 1)
	           factors.push_back (*ptr), k /= *ptr;

	     ptr++;
}

Vayamos a un caso práctico hace poco me encontre un problema en UVa llamado Factors and Factorials donde se pedía expresar el factorial de un número en sus factores primos. Recordemos que cuando multiplicamos dos números el resultado es la multiplicación de todos los números primos de ambos números es decir:

entonces si tenemos el factorial de un número, en realidad lo que es la multiplicación de todos los factores de el hasta 1 es decir

y así lo que podiamos hacer era precalcular todos los factores de cada número y el número nuevo sería la suma de estos más los de el mismo.

La solución al problema Factors and Factorials la pueden descargar desde aqui.

Espero que sea de alguna utilidad hasta la próxima entrada.

• 

Posts Relacionados

• Suma de dos números en base ‘n’ Tenemos dos números como cadena de caracteres, ambas en la...
• Sumar numeros muy grandes c++ Buenas. Resolviendo un pequeño problema me encontre con que debía...
• ¿Cuántas formas? Regreso con el arameo, escribí un problema hace unos días,...