[ Foro de C ]

descomponer en factores primos

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

gracias

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

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

Muchas gracias :)

saludos

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

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

#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;
}