
132 Chapitre 7 – Programmes d’arithm´etique
fonction facprem(N)
local D FACT
2->D
{} -> FACT
tant que N 6= 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
6 E(
√
N), soit D2 6 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
6 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
3etE(
√
N).
Dans la liste FACT, on fait suivre chaque diviseur par son exposant :
decomp(12)={2,2,3,1}.
Comentários a estes Manuais