Tester la primalité jusqu’à sqrt(n)
Vérifier efficacement un seul nombre
Tester la primalité jusqu’à sqrt(n) est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
La question des nombres premiers
Une compétence mathématique essentielle consiste à déterminer si un nombre donné est premier. Un nombre premier possède exactement deux diviseurs : un et lui-même. Vérifions-le rapidement. 🔍
La vérification naïve
Vous pourriez essayer de diviser n par tous les nombres de 2 à n moins 1. C'est correct, mais terriblement lent lorsque n est grand.
L'astuce de la racine carrée
Voici l'idée essentielle : il suffit de vérifier les diviseurs jusqu'à la racine carrée de n. Au-delà, aucun nouveau facteur ne peut apparaître.
Pourquoi la racine carrée suffit
Les diviseurs vont par paires dont le produit vaut n. S'ils étaient tous les deux supérieurs à la racine carrée, leur produit dépasserait n, ce qui est impossible.
La limite de la boucle
Faites varier i à partir de 2 tant que i fois i reste inférieur ou égal à n. Utiliser i*i évite les erreurs en virgule flottante dues à sqrt sur les grands entiers.
while i * i <= n:
...Gérez les petits cas
Les nombres inférieurs à 2 ne sont jamais premiers : rejetez-les donc immédiatement. Cette protection garde votre boucle principale claire et correcte.
if n < 2:
return FalseLa fonction complète
Assemblez le tout : protégez les petites valeurs, puis parcourez les diviseurs possibles jusqu'à la racine. Toute division exacte signifie que n est composé.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueAccélérez l'exécution
Traitez 2 séparément, puis ne testez que les nombres impairs. Ignorer les nombres pairs réduit de moitié environ le travail, sans complexité supplémentaire.
if n % 2 == 0:
return n == 2Le coût en temps
Cette vérification s'exécute en temps O(sqrt n). Pour un seul nombre inférieur ou égal à un milliard, cela représente seulement environ 30 000 opérations simples.
Un nombre, pas plusieurs
La vérification par racine carrée est idéale pour une ou quelques requêtes. Si vous avez besoin de tester la primalité sur toute une plage, un crible sera bien plus rapide.
Évitez le piège de la racine carrée
Comparer avec i*i plutôt qu'avec math.sqrt permet d'éviter les erreurs d'arrondi qui pourraient accepter ou rejeter à tort des nombres limites.
Vérification rapide
Confirmez la limite qui rend cette vérification rapide.
Récapitulatif
Vous pouvez maintenant vérifier la primalité d'un nombre en temps O(sqrt n), protéger les petites valeurs, ignorer les nombres pairs et utiliser i*i pour rester exact. ✅
Questions Fréquemment Posées
La leçon « Tester la primalité jusqu’à sqrt(n) » est-elle gratuite ?
Oui — le texte complet de « Tester la primalité jusqu’à sqrt(n) » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Tester la primalité jusqu’à sqrt(n) » ?
Vérifier efficacement un seul nombre Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Tester la primalité jusqu’à sqrt(n) » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- GCD, LCM et algorithme d’Euclide
- Tester la primalité jusqu’à sqrt(n)
- Crible d’Ératosthène
- Factorisation première et diviseurs