(* Décomposition en facteurs premiers *)

(* on cherche le premier facteur premier venu, il est renvoyé sous forme 
(p,quotient) ce qui amorce la liste de listes que sera la dfp *)

let premier_fp m=
	let racm=int_of_float(sqrt(float_of_int m)) in
	let rec essaye k = 
		if k>racm 
		then (m,1)
		else 	if (m mod k)=0 
			then (k,m/k)
			else essaye (k+2)
	in	if (m mod 2)=0 then (2, m/2) else essaye 3
;;
 
(* avance_dfp k liste connait deja les facteurs premiers présents dans liste, 
il va lui adjoindre le premier des facteurs premiers de k, sauf k=1 *)

let dec_fp n=
	let rec avance_dfp k liste=
		if k=1 
		then 	liste
		else 	let (p,m)= premier_fp k in
			match liste with
				|[]->avance_dfp m [(p,1)] 
				|(a,b)::q->	if p=a
						then avance_dfp m ((a,b+1)::q)
						else avance_dfp m ((p,1)::liste)
	in avance_dfp n [] 
;; 

(* une "évidente amélioration" consistera à faire démarrer premier fp d'un 
entier "départ" qui lui sera passé par avance dfp comme étant le premier de
la liste déja connue *)

let rec affiche_dfp l=
	match l with
		|[]->()
		|(a,b)::(c,d)::q -> begin
				print_string"(";
				print_int a;
				print_string"^";
				print_int b;
				print_string")*" end; affiche_dfp ((c,d)::q)
		|[(x,y)]-> 	begin
				print_string"(";
				print_int x;
				print_string"^";
				print_int y;
				print_string")" end; 
;;		
				
(* toutes ces fonctions semblent marcher, en fait elles auraient bien besoin 
de preuves de programme, c'est tout à fait dans ce type d'environnement que 
l'on a tendance à oublier des cas particuliers initiaux ou finaux *)

(* un test qui rate  *)
affiche_dfp (dec_fp 7500000000);;