Crible d’Ératosthène
Lister tous les nombres premiers jusqu’à N en temps quasi linéaire
Crible d’Ératosthène est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Les nombres premiers en grande quantité
Vous aurez parfois besoin de tous les nombres premiers jusqu'à N, et pas d'une seule vérification. Le crible d'Ératosthène les trouve tous en un seul balayage. 🧹
L'idée principale
Commencez par supposer que chaque nombre est premier. Ensuite, barrez les multiples de chaque nombre premier trouvé, en ne laissant que les véritables nombres premiers.
Initialisez les indicateurs
Créez une liste de booléens où l'indice i indique si i est premier. Ce tableau est la surface sur laquelle le crible opère.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseParcourez les candidats
Parcourez i en l'augmentant. La première fois que vous atteignez un nombre dont l'indicateur vaut encore True, il s'agit nécessairement d'un nouveau nombre premier sans facteur plus petit.
Barrez les multiples
Pour chaque nombre premier i, marquez 2i, 3i, 4i, etc. comme n'étant pas premiers. Ces multiples ont clairement i comme diviseur.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseCommencez à i au carré
Commencez à barrer à partir de i*i, et non de 2i. Chaque multiple plus petit a déjà été supprimé par un nombre premier précédent ; vous pouvez donc l'ignorer.
Arrêtez-vous à la racine
Il suffit d'appliquer le crible tant que i*i reste inférieur ou égal à N. Après la racine carrée, tout indicateur True restant correspond déjà à un nombre premier.
Le crible complet
Combinez le parcours extérieur et le marquage intérieur. Après la boucle, chaque indice dont l'indicateur vaut encore True correspond à un nombre premier confirmé.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseRassemblez les nombres premiers
Lisez les indicateurs finaux dans une liste à l'aide d'une compréhension. Vous disposez maintenant de tous les nombres premiers jusqu'à N, prêts pour des requêtes rapides.
primes = [i for i, p in enumerate(is_prime) if p]Pourquoi cette méthode est rapide
Le crible s'exécute en environ O(n log log n), soit un temps presque linéaire. C'est pourquoi il est nettement plus efficace que de tester plusieurs nombres un par un.
Surveillez la mémoire
Le tableau d'indicateurs utilise une quantité de mémoire proportionnelle à N. Pour de très grandes limites, vérifiez votre budget d'espace avant l'allocation.
Vérification rapide
Rappelez-vous la petite optimisation de la boucle intérieure.
Récapitulatif
Vous pouvez maintenant construire un crible pour lister tous les nombres premiers jusqu'à N en temps presque linéaire, en commençant chaque nombre premier à i*i et en vous arrêtant à la racine. ✅
Questions Fréquemment Posées
La leçon « Crible d’Ératosthène » est-elle gratuite ?
Oui — le texte complet de « Crible d’Ératosthène » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Crible d’Ératosthène » ?
Lister tous les nombres premiers jusqu’à N en temps quasi linéaire Tu pratiques Coding Interview Prep 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep 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 3 sur 4.
Combien de temps prend la leçon « Crible d’Ératosthène » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep 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