HP Calculatrice graphique HP 39g - Manuel (Page 132)

132 Chapitre 7 – Programmes d’arithm´etique
fonction facprem(N)
local D FACT
2 -> D
{} -> FACT
tant que N = 1 faire
si N mod D = 0 alors
FACT + D -> FACT
N/D -> N
sinon
D+1 -> D
fsi
ftantque
r´
esultat FACT
ffonction
- Premi`ere am´elioration
On ne teste que les diviseurs D entre 2 et E( √
N ).
En effet si N = D1
∗ D2 alors on a :
soit D1 E(
√
N ), soit D2 E(
√
N ) car sinon on aurait :
D1
∗ D2 (E(
√
N ) + 1) 2 > N .
fonction facprem(N)
local D FACT
2 -> D
{} -> FACT
tant que D*D N faire
si N mod D = 0 alors
FACT + D -> FACT
N/D-> N
sinon
D+1 -> D
fsi
ftantque
FACT + N -> FACT
r´
esultat FACT
ffonction
- Deuxi`eme am´elioration
On cherche si 2 divise N, puis on teste les diviseurs impairs D entre
3 et E(
√
N ).
Dans la liste FACT, on fait suivre chaque diviseur par son exposant :
decomp(12)=
{2,2,3,1}.