2votos

Factores primos en C

por josejuan hace 5 años

La forma más "rápida" de factorizar un único número viene a ser básicamente ésta.

Descomponer un numero positivo (>0) para obtener todos sus divisores.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
 
int main(int argc, char **argv) { 
    int n = atoi(argv[1]), z = 2, l = (int) sqrt(n); 
    while(n > 1 && z <= l) { 
        if(n % z == 0) { 
            printf("%i, ", z); 
            n /= z; 
            // actualizar 'l' si se quiere (compuesto de primos grandes) 
        } else 
            z++; 
    if(n > 1) 
        printf("%i", n); 
    printf("\n"); 
    return 0; 
 
// Que es instantáneo para cualquier número dentro de {{2^31}}, por ejemplo: 
 
[josejuan@centella tmp]$ gcc -O3 -lm f.c 
[josejuan@centella tmp]$ time -f "%E, %M" ./a.out 2000000011 
2000000011 
0:00.00, 548 
[josejuan@centella tmp]$ time -f "%E, %M" ./a.out 2012345678 
2, 7, 143738977 
0:00.00, 548 
10 comentarios
0votos

Escrito por adr hace 5 años

Me gusta. Obvio la salida será más rápida al hallar raíz de N. Es el primer código de descomposición que aplica la demostración de Al-Marrakushi Ibn al-Banna. Ahí va un +1.
0votos

Escrito por drabor hace 5 años

Muy bueno!
Aplicando sqrt(n) en vez de n reduzco el tiempo de mi solución a 3.5 ms!
No sé por qué, estaba convencidísimo que no podía ser sqrt(n), ej:
sqrt(92) < 23, que es un factor primo # nah, no puede ser sqrt(92), lo dejo en 92
Siendo el último factor primo el propio n!
0votos

Escrito por josejuan hace 5 años

El tema está, en que si es compuesto, es de la forma:
n = a * b

donde no pueden ser simultáneamente (ahí está la gracia) tanto a como b menores que la raíz cuadrada de n (si los dos son mayores que la raíz de n ¡ambos multiplicados son mayores que n!).

Así, primero encontraremos el primo menor y luego el proceso se repite para lo que queda del número.

;
0votos

Escrito por josejuan hace 5 años

"menores que la raíz cuadrada"

(no pueden ser mayores...)
0votos

Escrito por adr hace 5 años

menor IGUAL! (numeros inferiores o iguales a la raíz cuadrada de N)
Si N es mayor que 1, entonces N contiene el último de los factores primos.
0votos

Escrito por josejuan hace 5 años

No poder ser mayor equivale a tener que ser menor o igual.
0votos

Escrito por timelord117 hace 5 años

sacar la raiz fue muy ingenioso. lo compartire en fb
0votos

Escrito por javiergarciarajoy hace 5 años

Hola, espero no meter la pata, lo mío no es c (yo soy de fortran), ya puedes pasar de comprobar con los n pares distintos de 2 (así solo divides por la mitad de números).
0votos

Escrito por josejuan hace 5 años

Supongo que te refieres a los z pares, z = 2, 3, 4, 5, ... ; y usar doble incremento z += 2 a partir de z=3.

Es correcto lo que dices, aunque hay muchas otras que podríamos hacer (precalcular los primos y sólo hacer z=primo[q++], ciclos, etc...), y como escribí "viene a ser básicamente ésta".
0votos

Escrito por javiergarciarajoy hace 5 años

Correcto, gracias por la respuesta, por cierto, estoy con haskell en los ratos libres y de vez en cuando miro alguna de tus soluciones, sigue así. Un saludo

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.