Décomposition (judicieuse) en facteurs premiers

Contenu du snippet

Voici un algorithme consacré à la décomposition en facteurs premiers. D'abord, l'idée m'est venue de diviser par tous les nombres. Mais, bien entendu, c'est un algorithme naïf. Après réflexion, l'idée m'est venue de recourir à une suite de nombres premiers... parce que, hormis 2 et 3, tout nombre premier se note sous la forme 6p + 1 ou 6p + 5 (p un entier naturel) :

6*0 + 5 = 5
6*1 + 1 = 7
6*1 + 5 = 11 etc...

Remarquons toutefois que la réciproque est fausse : Tout nombre de la forme 6p + 1 ou 6p + 5 n'est pas nécessairement premier. Par exemple 25 = 6*4 + 1.
Ensuite, notons ceci :

Si mon nombre premier est de la forme 6p + 1, alors 6p + 1 + 4 = 6p + 5
Si mon nombre premier est de la forme 6p + 5, alors 6p + 5 + 2 = 6(p + 1) + 1

Remarquons en outre l'alternance du 2 et du 4 :

5 + 2 = 7
7 + 4 = 11
11 + 2 = 13
13 + 4 = 17
17 + 2 = 19
19 + 4 = 23
23 + 2 = 25 (un terme "inutile", qui justifie la remarque sur la réciproque...)

Initialisons la suite des nombres premiers par N = 5. Posons J = -2 et M = 2.

1er calcul
Soit N = N + M. On en conclut que N = 7
Soit J = -J. On en conclut que J = 2
Soit M = M + J. On en conclut que M = 4

2ème calcul
Soit N = N + M. On en conclut que N = 11
Soit J = -J. On en conclut que J = -2
Soit M = M + J. On en conclut que M = 2

3ème calcul
Soit N = N + M. On en conclut que N = 13
Soit J = -J. On en conclut que J = 2
Soit M = M + J. On en conclut que M = 4

et ainsi de suite...

Nous construisons ainsi une suite contenant tous les nombres premiers p tels que p > 3... et quelque autres nombres "inutiles" comme 25 par exemple. Il ne reste plus qu'à diviser par chacun de ces termes et enregistrer, selon la méthode classique, les diviseurs avec gestion des exposants (le résultat étant de type String).

Source / Exemple :


'Placer ceci dans un module (test avec Sub Main) :

Option Explicit

    Dim A As Long, N As Long, M As Long, I As Long, J As Long, U As Long
    Dim S As String

'Diviser par tous les nombres revient à diviser 
'par un nombre conséquent de nombres inutiles.
'L'idée est de diviser selon une suite de nombres
'premiers. Remarquons que, hormis 2 et 3, tout 
'nombre premier se note 6p + 1 ou 6p + 5. 
'Remarque : tout nombre premier se note 
'de cette forme, mais tout nombre de cette
'forme n'est pas nécessairement premier !

Public Function DFP(ByRef A As Long) As String
    'Sauvegarde de la valeur
    Let U = A
    'Division par deux (premier cas particulier)
    Let N = 2
    A = Diviser(A, N)
    'Division par trois (second cas particulier)
    Let N = 3
    A = Diviser(A, N)
    'Voici la partie la moins triviale. 
    'Remarquons que 5 + 2 = 7, 
    '7 + 4 = 11, 11 + 2 = 13, 
    '13 + 4 = 17... D'une manière
   'générale : Si le nombre se note 
    '6p + 1, alors 6p + 1 + 4 = 6p + 5
   'Si le nombre se note 6p + 5, alors 
    '6p + 5 + 2 = 6(p + 1) + 1. Maintenant,
    'comment obtenir 2 et 4 avec un seul 
    'calcul ? Soit N le diviseur. Le suivant 
    'est donné par N + M, et M prend pour
    'valeur deux ou quatre selon que J = 2
    'ou J = -2...
    Let N = 5
    Let M = 2
    Let J = -2
    Do
        A = Diviser(A, N)
        Let N = N + M
        Let J = -J
        Let M = M + J
    Loop While N <= Sqr(A)
    If S <> "" Then S = S & " * "
    If A <> 1 Then S = S & A
    DFP = "Résultat : " & U & " = " & S
End Function

Private Function Diviser(ByRef A As Long, ByVal N As Long) As Long
  'Initialisation du compteur d'exposant
  I = 0
  'Tant que N | A, augmenter le compteur 
   'd'exposant et diviser A
  While A Mod N = 0
    I = I + 1
    Let A = A / N
  Wend
  'Quand I n'est pas nul, ajouter
  'la valeur à la chaîne
  'Ajouter * quand la chaîne n'est
  'pas vide, et l'exposant
  's'il est supérieur ou égal à 1
    If I <> 0 Then
      If S <> "" Then S = S & " * "
      If I = 1 Then
          S = S & N
      Else
          S = S & N & "^" & I
      End If
    End If
    'Renvoyer A pour la suite du calcul
    Diviser = A
End Function

Conclusion :


Voilà donc une astuce pour calculer vite... j'espère que cela sera utile.

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.