/* Muestra la descomposicion en numeros primos del numero ingresado */
/* El output es de la forma:                                        */
/* a = (p_1 ** n_1) * (p_2 ** n_2) * ..... * (p_t ** n_t)           */
/* donde a es el numero ingresado                                   */
/*       p_i son numeros primos                                     */
/*       n_i es el exponente asociado a cada primo (la cantidad de  */
/*           veces que aparece en la descomposicion)                */
/*                                                                  */
/* Santiago Bruno - 2005 - bananabruno@hotmail.com                  */
/* http://www.santiagobruno.com.ar/programas.html                   */

#include <stdio.h>
#include <math.h>
#define MAX_PRIMOS 100
#define MAX_LENGTH 100

typedef struct {
    int numero;
    int veces;
} primos;

void agregar(primos list[], int *i, int *primoscnt);

int main() {

primos list[MAX_PRIMOS];
int primo, i;
int primoscnt = 0, cnt;
int raiz, found;
char* primo_str[MAX_LENGTH];

printf("Ingrese el numero: ");
scanf("%s",primo_str);
primo = atoi(primo_str);

while (primo < 2) {
    printf("Ingrese un numero mayor que 1: ");
    scanf("%s",primo_str);
    primo = atoi(primo_str);
}


raiz = (int)(sqrt((float)primo)) + 1;
/*printf("La raiz: %d\n",raiz);*/

printf("%d = ",primo);

i = 2;

while ((i <= raiz) && (primo >= 2)) {
    if (primo%i == 0) {
	/* agregar a la lista */
	agregar(list,&i,&primoscnt);
	primo = primo / i;
    
    }
    else {
	/* siguiente prueba */
	if (i != 2) {i = i + 2;}
	else {i = i + 1;}   
    
    }

}


if (i > raiz) {
    agregar(list,&primo,&primoscnt);
}


/* mostrar descomposicion */

i = 0;
while (i < primoscnt) {
    
    if (i != (primoscnt - 1)) {
	printf("(%d ** %d) * ",list[i].numero,list[i].veces);
    }
    else {
	printf("(%d ** %d)\n",list[i].numero,list[i].veces);
    }
    
    i++;
}


return 0;
}


void agregar(primos list[], int *i, int *primoscnt) {
int cnt, found;

	cnt = 0;
	found = 0;
	while ((cnt < *primoscnt) && (!found)) {
	    if (list[cnt].numero == *i) {
		list[cnt].veces++;
		found = 1;	    
	    }
	    else {cnt ++;}
	}
	if (!found) {
	    list[cnt].numero = *i;
	    list[cnt].veces = 1;
	    (*primoscnt)++;
	}


}