Tester si un nombre est premier en Python
Dans cette leçon, vous allez vérifier si un nombre est premier en ne testant les diviseurs que jusqu'à sa racine carrée.
Introduction
Le problème
Les nombres premiers sont derrière le chiffrement sur internet, les tables de hachage et beaucoup d'énigmes. Tester si un nombre est premier en essayant chaque diviseur jusqu'au nombre lui-même marche pour 29, mais devient terriblement lent pour de grands nombres. Une petite idée rend le test bien plus rapide.
Imaginez-le ainsi
Chercher des diviseurs, c'est comme essayer de poser des carreaux pour former un rectangle complet. 36 carreaux se posent en 1×36, 2×18, 3×12, 4×9 et 6×6. Après le carré (6×6), on retrouve les mêmes rectangles, simplement tournés : il n'y a donc rien de nouveau à chercher au-delà de la racine carrée. 29 carreaux ne se posent qu'en 1×29, donc 29 est premier.
number > 1🚪 Seuls les nombres supérieurs à 1 peuvent être premiersdivisor * divisor <= number🪞 S'arrêter au carré : les rectangles suivants sont des répétitionsnumber % divisor == 0🔍 Un rectangle complet tient : pas premierdivisor += 1➡️ Essayer la largeur suivanteUn nombre premier est un entier supérieur à 1 dont les seuls diviseurs positifs sont 1 et lui-même.
Points clés
is_prime = number > 1commence à False pour 0, 1 et les nombres négatifs, qui ne sont jamais premiers.while divisor * divisor <= number and is_prime:s'arrête à la racine carrée ou dès qu'un diviseur est trouvé.number % divisor == 0signifie quedivisordivise exactement le nombre.- Pour 29, la boucle n'essaie que 2, 3, 4 et 5 avant de pouvoir dire que le nombre est premier.
Quand l’utiliser ?
- Les énigmes et exercices sur les nombres, comme lister les nombres premiers ou trouver les facteurs premiers.
- Comprendre pourquoi s'arrêter tôt et ne tester que jusqu'à une limite accélère les boucles.
- Valider une saisie dans des outils de maths.
Quand s'en passer
- Lister tous les nombres premiers jusqu'à une grande limite : le crible d'Ératosthène est bien plus rapide que de tester chaque nombre.
- La cryptographie avec des nombres de centaines de chiffres : les vrais systèmes utilisent des tests probabilistes.
Code d’exemple
number = 29
is_prime = number > 1
divisor = 2
while divisor * divisor <= number and is_prime:
if number % divisor == 0:
is_prime = False
divisor += 1
print(f"{number} is prime: {is_prime}")
Résultat de l’exécution
29 is prime: True
Explication du code
La boucle n'a besoin de tester les diviseurs que tant que divisor * divisor <= number. En effet, si n a un diviseur supérieur à sa racine carrée, celui-ci est forcément associé à un diviseur plus petit que la boucle a déjà testé. La complexité tombe ainsi à O(√n), et le résultat montre que 29 est premier.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Changez les données d’entrée et prévoyez le résultat avant d’exécuter.
- Ajoutez une vérification pour les données vides ou invalides.
- Placez le traitement dans une fonction séparée et testez-la avec plusieurs jeux de données.
Erreurs fréquentes
Considérer 1 comme premier
1 n'a qu'un seul diviseur, il n'est donc pas premier. Testez d'abord number > 1.
is_prime = True # 1 would be reported as prime
is_prime = number > 1
Boucler jusqu'au nombre lui-même
Cela donne la bonne réponse mais essaie bien plus de diviseurs que nécessaire.
for divisor in range(2, number):
while divisor * divisor <= number:
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Vérification de nombre premier Déterminez si un nombre est premier. Facile
- Plus grand facteur premier Trouver le plus grand nombre premier qui divise un entier positif. Moyen
- Lister les nombres premiers avec un crible Trouvez les nombres premiers jusqu'à une limite en marquant les multiples composés. Moyen