Exercices Python pour débutants

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.

  • Débutant
  • 2 min de lecture
  • 1 exemple exécutable

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.

Des rectangles de carreaux au code
number > 1🚪 Seuls les nombres supérieurs à 1 peuvent être premiers
divisor * divisor <= number🪞 S'arrêter au carré : les rectangles suivants sont des répétitions
number % divisor == 0🔍 Un rectangle complet tient : pas premier
divisor += 1➡️ Essayer la largeur suivante
Si aucun diviseur n'est trouvé jusqu'à la racine carrée, le nombre est premier.
En une phrase

Un nombre premier est un entier supérieur à 1 dont les seuls diviseurs positifs sont 1 et lui-même.

Points clés

  1. is_prime = number > 1 commence à False pour 0, 1 et les nombres négatifs, qui ne sont jamais premiers.
  2. while divisor * divisor <= number and is_prime: s'arrête à la racine carrée ou dès qu'un diviseur est trouvé.
  3. number % divisor == 0 signifie que divisor divise exactement le nombre.
  4. 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

Exécuter le code →
main.py
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}")
Obtenir un bouton Run pour cet exemple

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.

  1. Changez les données d’entrée et prévoyez le résultat avant d’exécuter.
  2. Ajoutez une vérification pour les données vides ou invalides.
  3. Placez le traitement dans une fonction séparée et testez-la avec plusieurs jeux de données.
Exécuter dans le compilateur Python →

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.

Problème
is_prime = True  # 1 would be reported as prime
Correction
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.

Problème
for divisor in range(2, number):
Correction
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.

Tous les défis