Générateur du Crible d'Ératosthène (Gratuit) – Liste de nombres premiers et N-ième premier

Indiquez une limite supérieure N pour générer une liste de nombres premiers avec le Crible d'Ératosthène, visualisée étape par étape. Recherchez aussi le N-ième nombre premier (jusqu'au 1 000 000e) — gratuit, dans le navigateur, sans inscription.

Crible d'Ératosthène de 1 à 100 (tableau de référence)

Les cellules vertes sont des nombres premiers ; les autres ont été éliminées par le crible.

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

1 n'est ni premier ni composé, il n'est donc pas coloré.

Conseils

  • Le Crible d'Ératosthène liste efficacement tous les nombres premiers jusqu'à N en barrant les multiples de chaque premier trouvé, à partir de 2.
  • Réglez la limite supérieure N à 400 ou moins pour voir exactement quel premier a éliminé quel nombre, étape par étape.
  • La recherche du N-ième premier prend en charge des requêtes comme « quel est le 1 000 000e nombre premier », utile pour confirmer l'existence de très grands nombres premiers.
  • Tout s'exécute localement dans votre navigateur — la liste de premiers générée n'est jamais envoyée à un serveur.

Questions fréquentes

C'est une méthode de recensement des nombres premiers attribuée au mathématicien du IIIe siècle av. J.-C. Ératosthène. À partir de 2, on barre mécaniquement les multiples de chaque premier trouvé ; ce qui reste est premier. Comme elle ne nécessite que des opérations simples répétées, elle se prête bien à une implémentation informatique.

Comme tout le calcul s'exécute dans votre navigateur, la limite supérieure est plafonnée à 1 000 000. Aller au-delà augmenterait fortement la charge de calcul et pourrait rendre le navigateur peu réactif.

Le théorème des nombres premiers fournit une estimation de la limite supérieure du N-ième premier, et le crible est exécuté sur cette plage pour le trouver exactement. Les recherches sont prises en charge jusqu'au 1 000 000e nombre premier.

Lorsqu'il y a de nombreux résultats, seuls les 1 000 premiers sont affichés, le reste étant résumé par un nombre. La visualisation étape par étape n'est disponible que pour des limites supérieures de 400 ou moins.
ツールくん

Anecdote — Pourquoi un algorithme vieux de 2 000 ans est encore utilisé

Le Crible d'Ératosthène est l'un des plus anciens algorithmes de génération de nombres premiers encore connus, attribué au savant grec Ératosthène, qui fut bibliothécaire en chef de la Bibliothèque d'Alexandrie au IIIe siècle av. J.-C. Le fait qu'une méthode conçue il y a plus de deux mille ans soit encore enseignée aujourd'hui dans les cours d'informatique témoigne de son élégante simplicité.

Le mécanisme est étonnamment simple : on liste les entiers à partir de 2, on considère le plus petit nombre non encore marqué comme premier, et on barre tous ses multiples. En répétant cette opération jusqu'à √N, tous les nombres premiers jusqu'à N sont révélés. Pour générer une liste complète de premiers, c'est bien plus efficace que de tester chaque nombre individuellement par division d'essai.

La recherche de nombres premiers gigantesques se poursuit aujourd'hui — des projets de calcul distribué comme GIMPS (Great Internet Mersenne Prime Search) continuent de découvrir des nombres premiers de Mersenne comptant des dizaines de millions de chiffres. Le crible lui-même n'est pas utilisé pour trouver des premiers aussi grands, mais son idée centrale — éliminer mécaniquement les multiples — sous-tend des algorithmes de test de primalité plus avancés.

Voir toutes les anecdotes

Les personnes ayant consulté cet outil ont aussi consulté

Vérificateur de nombres premiers — Étapes et factorisation

Vérifiez si un nombre (jusqu'à 10 000 000) est premier. Voir les étapes de division, la factorisation complète et le nombre premier précédent/suivant. Gratuit.

Décomposition en facteurs premiers (jusqu'à 1 000 000)

Décomposez instantanément tout entier N (de 2 à 1 000 000) en facteurs premiers. Affiche la division étape par étape, les diviseurs, leur nombre et leur somme. Table de référence 1–100 incluse.

Calculateur de PGCD et PPCM

Saisissez deux entiers positifs pour trouver leur plus grand commun diviseur (PGCD) grâce à l'algorithme d'Euclide, avec chaque étape du calcul affichée. Le plus petit commun multiple (PPCM) est calculé en même temps.

Calculateur d'arithmétique modulaire (calculateur de mod)

Un calculateur d'arithmétique modulaire proposant 4 modes : mod de base, addition/soustraction/multiplication modulaire, exponentiation modulaire (exponentiation rapide par élévations au carré successives) et inverse mod...

Calculateur du théorème des restes chinois (TRC) — Résoudre des congruences simultanées

Résout un système de congruences simultanées x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... grâce au théorème des restes chinois. Vérifie automatiquement que les modules sont premiers entre eux deux à deux et fournit la plus petite...

Calculateur de l'indicatrice d'Euler (fonction φ)

Saisissez un entier N (1 à 1 000 000) pour calculer instantanément combien d'entiers entre 1 et N sont premiers avec N (indicatrice d'Euler φ(N)), avec la décomposition en facteurs premiers et la formule utilisée. Compre...