[ Foro de C ]

descomponer en factores primos

02-Dec-2010 16:29
Diego Fernández
6 Respuestas

¿Como puedo crear un programa que descomponga un número como producto de sus factores primos?

gracias


03-Dec-2010 00:30
Carlos Ruiz

Holap:

Hay muchas maneras de hacerlo, aquí te dejo un ejemplo:


/*******************FACTORES PRIMOS***********************/
#include <stdio.h>

int numero=1234567890;  //El numero que examinaremos.
int factores[1000];     //Arreglo para almacenar factores de "numero".
int i_factores=0;       //Indice para recorrer el arreglo "factores[]".


int main(){
    
int i=2;             //Empezaremos a verificar todos los factores desde 2.
                     //Pues el numero 1 es factor de todos los numeros.
  while(i<=numero)
  {
    if((numero%i)==0)  //a%b=0, implica que b es factor de a.
    {
    factores[i_factores]=i;  //Añadimos el factor al arreglo.
    numero=numero/i;         //Procesamos la variable "numero".
    i_factores++;            //Incrementamos indice de arreglo para el siguiente numero.
    continue;
    }     
  i++;  //Incrementamos indice.
  }

/* Rutina para imprimir */
i=0;   
printf("1 "); 
  while(i<i_factores)
  {
  printf(" %d ", factores[i]);
  i++;
  }
       
return 0;
}

/************************************************************/


Saludooos :P


03-Dec-2010 00:43
Carlos Ruiz

Aquí puedes ver que efectivamente funciona:

http://codepad.org/bRejemsW

Si no te gusta que muestre varias veces un mismo factor, existen varias maneras de hacer que sólo muestre una vez cada uno... pero esa es una tarea que tú debes realizar... ;)

Saludooos :P


03-Dec-2010 09:00
Diego Fernández

Muchas gracias :)

saludos


05-Dec-2010 10:26
Nacho Cabanes (+84)

La solución de Carlos es buena, pero tiene un riesgo: usa arrays, por lo que necesita ocupar más espacio en memoria que si mostrara directamente en pantalla. Además, siempre está el riesgo de desbordar el array si la cantidad de factores es muy grande.

Una alternativa es mostrar los datos directamente en pantalla a medida que los calculas.

En cuanto al algoritmo, se puede plantear también tal y como lo resolverías "a lápiz": divido entre dos mientras que sea divisible; cuando ya no sea posible, paso a probar el tres; cuando ya no sea posible...

En ese caso, la solución podría ser así:


#include <stdio.h>

int main() {
     int numero, divisor = 2;
     
     puts("Dime un numero: ");
     scanf("%d", &numero);
     printf("%d = ",numero);
     
     while ( numero >= divisor ){            
          while ( numero % divisor == 0 ) {
              printf("%d x ",divisor);   
              numero = numero / divisor;    
          }
          divisor ++;
     }
     printf("%d",numero);
     
}


Y un ejemplo de su resultado podría ser

19079620 = 2 x 2 x 5 x 7 x 7 x 19469 x 1


05-Dec-2010 17:23
Carlos Ruiz

En este caso, la propuesta de Nacho de mostrar directamente los números en la pantalla es mucho mejor que la mía, pues no tiene sentido almacenar los factores, ya que no les daremos ningún otro uso (según lo que se nos ha pedido).

Aún así, estimado Nacho, en este caso particular el uso de arreglos es bastante poco riesgoso, pues en un PC de 32 bits, la mayor cantidad posible de factores primos es 33 (32 veces "2" y 1 vez el factor "1") así como en un PC de 64 bits, la mayor cantidad es 65.

Por lo tanto, con un arreglo que pueda contener 70 unsigned int estamos listos... y el uso de memoria RAM sería razonable.

Saludoooos :P


01-Sep-2014 08:39
Invitado (uno más eficiente)



#include <stdio.h>
#include <string.h>

#define MAX 10000

void genera_primos(int *criba)
{
    int i,j;
    for(i=2;i*i<=MAX;i++)
        if(!criba[i])
            for(j=i*i;j<MAX;j+=i)
                if(!criba[j]) criba[j]=i;
}

void fact(int *criba,int n)
{
    int i;
    for(i=n;criba[i];i=i/criba[n])
        printf("%d ",criba[i]);
    printf("%d\n",i);
}

int main()
{
    int criba[MAX+1];
    int n;

    memset(criba,0,sizeof(criba));
    genera_primos(criba);

    scanf("%d",&n);
    fact(criba,n);

    return 0;
}







(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)