Les algorithmes et leurs traductions algorithmiques

• Premier algorithme
  Soit N un entier.
  On teste, pour tous les nombres D de 2 à N, la divisibilité de N par D.
  Si D divise N, on cherche alors les diviseurs de N/D etc...N/D joue le rôle de N et on s'arrête quand N = 1
  On met les diviseurs trouvés dans la liste FACT.

  fonction factprem(N)
  local D FACT 
  2 -> D
  {} -> FACT
  

  tantque N $\neq$ 1 faire

    si N mod D = 0 alors
     concat(FACT,D) -> FACT
      N/D -> N
     sinon
      D+1 -> D
   fsi
  ftantque
  retourne FACT
  ffonction
  

• Première amélioration
  On ne teste que les diviseurs D entre 2 et E($\sqrt{N}$).
  En effet si N = D1*D2 alors on a :
  soit D1 $\leq$ E($\sqrt{N}$), soit D2 $\leq$ E($\sqrt{N}$) car sinon on aurait :
  D1*D2 $\geq$ (E($\sqrt{N}$) + 1)² > N.

  fonction factprem1(N)
  local D FACT
  2 -> D
  {} -> FACT
  

  tantque D*D $\leq$ N faire

    si N mod D = 0 alors
      concat(FACT,D) -> FACT
      N/D-> N
     sinon
      D+1 -> D
   fsi
  ftantque
  concat(FACT,N) -> FACT
  retourne FACT
  ffonction
  

  Dans la liste FACT, on a les diviseurs premiers éventuellement plusieurs fois, par exemple :
  factprem1(12)={2,2,3}.
• Deuxième amélioration
  On cherche si 2 divise N, puis on teste les diviseurs impairs D entre 3 et E($\sqrt{N}$).

  Dans la liste FACT, on fait suivre chaque diviseur premier par son exposant, par exemple :
  factprem2(12)={2,2,3,1}.

  fonction  facprem2(N)
  local K D FACT
  {}->FACT
  0 -> K
  tantque N mod 2 = 0 faire
      K+1 -> K
      N/2 -> N
  ftantque
  

  si K $\neq$0 alors

     concat(FACT,{2 K}) -> FACT
  fsi
  3 ->D
  

  tantque D*D $\leq$ N faire

    0 -> K
    tantque N mod D = 0 faire
      K+1 -> K
      N/D -> N
    ftantque
  

  si K $\neq$0 alors

      concat(FACT,{D K}) -> FACT
    fsi
    D+2 -> D
  ftantque
  

  si N $\neq$ 1 alors

  concat(FACT,{N 1}) -> FACT
  fsi
  retourne FACT
  ffonction
  

• Troisième amélioration
  On cherche si 2 et 3 divisent N, puis on teste les diviseurs D entre 5 et E($\sqrt{N}$) de la forme 6*k - 1 ou 6*k + 1.
  On remarque que si :
  D = 6*k - 1 on a D + (4*D mod 6) = 6*k + 1
  et que si :
  D = 6*k + 1 on a D + (4*D mod 6) = 6*(k + 1) - 1
  Dans la liste FACT, on fait suivre chaque diviseur par son exposant, par exemple :
  factprem3(12)={2,2,3,1}.

  fonction  factprem3(N)
  local J,D,FACT 
  2->D
  {}->FACT
  tantque (D*D<=N) faire
   0->J
   tantque (N mod D=0) faire
     N/D->N
     J+1->J
   ftantque
  

  si (J $\neq$ 0) alors concat(FACT,{D,J})->FACT fsi

   si (D<4) alors 
     2*D-1->D
   sinon
     D+(4*D mod 6)->D
   fsi
  ftantque
  

  si (N $\neq$ 1) alors concat(FACT,{N,1})->FACT fsi
  retourne(FACT)
  ffonction