Diviseurs et nombres premiers
Les nombres premiers fascinent les mathématiciens depuis plus de 2 000 ans, et ils protègent aujourd'hui les paiements sur Internet. C'est aussi un terrain de jeu idéal pour l'algorithmique.
Les diviseurs d'un nombre
Un nombre d divise n quand la division tombe juste, c'est-à-dire quand le reste est nul : n mod d = 0.
n est un nombre
demande 'Un nombre entier ? ' dans n
affiche 'Diviseurs de ' + n + ' :'
pour d de 1 à n
si n mod d = 0 alors
affiche d
fin si
fin pour
Pour 12, le programme affiche 1, 2, 3, 4, 6 et 12. On essaie simplement tous les candidats de 1 à n : c'est la méthode dite de « force brute ».
Qu'est-ce qu'un nombre premier ?
Un nombre est premier s'il a exactement deux diviseurs : 1 et lui-même. Les premiers sont 2, 3, 5, 7, 11, 13... Attention, 1 n'est pas premier.
Première idée : compter les diviseurs.
fonction estPremier(n)
diviseurs est un nombre vaut 0
pour d de 1 à n
si n mod d = 0 alors
diviseurs ajoute 1
fin si
fin pour
retourne diviseurs = 2
fin fonction
affiche estPremier(13) // vrai
affiche estPremier(15) // faux
Ça marche, mais c'est du gaspillage : pour savoir que 1 000 000 n'est pas premier, la fonction fait un million de divisions, alors que la toute première (par 2) suffisait !
Question : Pourquoi 9 n'est-il pas un nombre premier ? — Parce qu'il est divisible par 3. 9 a trois diviseurs : 1, 3 et 9. Un nombre premier en a exactement deux.
Un algorithme plus malin
Deux améliorations :
- S'arrêter au premier diviseur trouvé : inutile de continuer.
- Ne tester que jusqu'à la racine carrée : si
n = a × b, l'un des deux est forcément plus petit ou égal à la racine de n.
fonction estPremier(n)
si n < 2 alors
retourne faux
fin si
d est un nombre vaut 2
tant que d * d <= n
si n mod d = 0 alors
retourne faux
fin si
d ajoute 1
fin tant que
retourne vrai
fin fonction
affiche 'Nombres premiers jusqu’à 50 :'
pour i de 1 à 50
si estPremier(i) alors
affiche i
fin si
fin pour
La condition d * d <= n revient à dire « tant que d ne dépasse pas la racine de n ». Pour tester 1 000 003, cette version fait environ 1 000 divisions au lieu d'un million : mille fois plus rapide !
Tu peux mesurer la différence avec chrono() : relève le temps avant et après, et affiche l'écart en millisecondes.
La décomposition en facteurs premiers
Tout nombre entier s'écrit comme un produit de nombres premiers : 60 = 2 × 2 × 3 × 5. L'algorithme : tant que le nombre est divisible par d, on le divise ; sinon, on passe au d suivant.
n est un nombre
demande 'Un nombre à décomposer ? ' dans n
d est un nombre vaut 2
facteurs est un texte vaut ''
tant que n > 1
si n mod d = 0 alors
facteurs ajoute d + ' '
n vaut n / d
sinon
d ajoute 1
fin si
fin tant que
affiche 'Facteurs premiers : ' + facteurs
Pour 60, le programme affiche 2 2 3 5.
En résumé
d divise n quand n mod d = 0.- Un nombre premier a exactement deux diviseurs : 1 et lui-même.
- S'arrêter dès qu'on a la réponse et tester jusqu'à la racine rend l'algorithme mille fois plus rapide.
- Un même problème peut avoir plusieurs algorithmes, plus ou moins efficaces.
