J'ai fait une procédure Maple (v11) pour trouver la décomposition en produit de puissances de facteurs premiers de tout entier naturel.
La voici :
prochainpremier:=proc(a::prime)
> p:=a+1;
> while irem((p-1)!,p)(p-1) do p:=p+1;od;
> p;
> end:
premierpremier:=proc(a::integer)
> n:=a;
> p:=2;
> while irem(a,p)0 do p:=prochainpremier(p); od;
> p;
> end:
premierpremierpuissance:=proc(a::integer)
> n:=a;
> p:=premierpremier(n);
> q:=premierpremier(n);
> m:=0;
> while irem(n,p)=0 do p:=p*q;od;
> m:=ln(p/q)/ln(q);
> m;
> end:
decompremier:=proc(a::integer)
> n:=a;
> p:=premierpremier(n);
> b:=premierpremierpuissance(n);
> m:=a/(p^b);
> L:=[p^{b}];
> while m>1 do L:=[op(L),premierpremier(m)^{premierpremierpuissance(m)}]; m:=m/(premierpremier(m)^premierpremierpuissance(m));od;
> L;
> end:
Et par exemple :
> decompremier(17^3*2^3*19);
[CENTER][2^{3}, 17^{3}, 19^{1}][/CENTER]
> decompremier(126842);
[CENTER][2^{1}, 63421^{1}][/CENTER]
Pour le premier exemple, ca va très vite, mais pour le second (j'ai tapé un nombre au hasard du clavier) ca met 80 secondes environ et si je rajoute encore plusieurs chiffres mon PC n'a pas assez de mémoire !
Donc j'aimerais savoir si mon algorithme est optimisable en gardant a peu près les mêmes idées, ou si je dois plutôt chercher des exemples d'algorithmes faits par d'autres pour voir s'ils vont plus vite (ou s'il faut que j'achète un PC à la NASA !) ?
Merci pour vos réponses...
NB : J'ai utilisé le théorème de Wilson pour la procédure "prochain premier".
le "!" de fatal_error, c'est pour dire "différent de". En maple, cela s'écrit "".