Tester si un nombre est premier
Entrez un entier positif pour savoir immédiatement s'il est premier, obtenir sa décomposition en facteurs premiers, le nombre et la somme de ses diviseurs, ainsi que ses voisins premiers. Algorithme optimisé par roue de factorisation — résultat instantané jusqu'à 10 milliards.
Entiers de 2 à 10¹³. La décomposition reste instantanée jusqu'à ~10¹⁰.
Historique des tests
Toutes les cellules sont modifiables — annotez vos recherches.
| Nombre | Verdict | Décomposition | Note |
|---|
Nombres premiers remarquables — cliquez pour tester
Nombres composés intéressants
Ce qu'un test de primalité ne fait pas — et ce que ça implique pour vous
La plupart des ressources en ligne se contentent d'expliquer la définition d'un nombre premier. Elles passent sous silence la question centrale : à quelle vitesse peut-on tester un nombre, et jusqu'où cet outil peut-il aller ? Comprendre les algorithmes derrière le test, c'est comprendre les limites et savoir quand le résultat est fiable.
Point de rupture critique : Pour un entier n, la division d'essai naïve teste tous les diviseurs jusqu'à √n. Pour n = 10¹², cela représente 10⁶ divisions — exécutables en quelques millisecondes en JavaScript. Pour n = 10¹⁸, on passe à 10⁹ divisions — environ 10 secondes de calcul dans un navigateur. Cet outil utilise une roue de factorisation mod 30 qui élimine d'emblée 73,3 % des candidats, abaissant le seuil de confort à 10¹³.
Les trois familles d'algorithmes de primalité : choix selon le contexte
Il n'existe pas un seul test de primalité mais une famille d'algorithmes, chacun adapté à une plage de nombres et à un niveau de certitude requis. Le choix de l'algorithme détermine la vitesse, la certitude du résultat et la complexité d'implémentation.
| Algorithme | Plage optimale | Certitude | Complexité |
|---|---|---|---|
| Division d'essai | n < 10¹⁰ | 100 % (déterministe) | O(√n) |
| Roue mod 2·3·5 | n < 10¹³ | 100 % (déterministe) | O(√n / 3,75) |
| Miller-Rabin (k tours) | n quelconque | Probabiliste (1 − 4⁻ᵏ) | O(k · log²n) |
| Miller-Rabin déterministe | n < 3,3 × 10²⁴ | 100 % (bases fixes) | O(log²n) |
| AKS (Agrawal-Kayal-Saxena) | n quelconque | 100 % (déterministe) | O(log⁶n) |
| ECPP (courbes elliptiques) | Très grands premiers | 100 % avec certificat | Heuristique O(log⁵n) |
Ce que fait cet outil concrètement
Roue de factorisation mod 30
Parmi les entiers de 1 à 30, seuls 8 ne sont divisibles ni par 2, ni par 3, ni par 5 : {1, 7, 11, 13, 17, 19, 23, 29}. Tout nombre premier > 5 est congru à l'un de ces 8 résidus modulo 30.
| Candidats testés / 30 entiers | 8 (26,7 %) |
| Gain vs division naïve | ×3,75 plus rapide |
| Gain vs test impairs seuls | ×1,875 plus rapide |
| Résultat pour n = 10¹³ | < 500 ms dans le navigateur |
3 domaines où la primalité a des conséquences économiques directes
Domaine 1 — Cryptographie RSA : les nombres premiers qui protègent vos paiements en ligne
Chaque connexion HTTPS repose sur RSA ou son successeur, dont la sécurité tient à l'impossibilité pratique de factoriser le produit de deux grands nombres premiers. En 2026, les recommandations ANSSI et NIST exigent des modules RSA d'au moins 3 072 bits pour les systèmes à long terme.
| Taille des premiers RSA (2048 bits) | Environ 10³⁰⁸ chiffres décimaux |
| Meilleur algorithme de factorisation | Crible du corps de nombres (GNFS) — O(exp(∛n)) |
| Temps pour factoriser RSA-2048 | > 10¹⁰ années avec les ordinateurs classiques |
| Menace quantique (algorithme de Shor) | Théoriquement O(log³n) — mais nécessite > 4 000 qubits logiques stables |
| Horizon de migration post-quantique (NIST) | 2030 pour les systèmes critiques (CRYSTALS-Kyber, Dilithium) |
Le test de primalité est l'étape 1 de la génération de clé RSA. Chaque navigateur web génère des nombres premiers de 1 024 à 4 096 bits à chaque session TLS — des millions de fois par seconde à l'échelle mondiale.
Domaine 2 — Hachage et tables de hachage : pourquoi les développeurs choisissent des tailles premières
Dans les structures de données (HashMap en Java, dict en Python, tables SQL), la taille interne du tableau sous-jacent est souvent un nombre premier. Ce n'est pas une superstition : c'est une propriété arithmétique qui minimise les collisions par une répartition uniforme des clés.
| Taille 16 (puissance de 2) | Les clés multiples de 4 tombent toutes dans 4 cases seulement |
| Taille 17 (premier) | Aucun diviseur commun avec la plupart des clés → répartition uniforme |
| Taille Redis par défaut (dict) | 4, 8, 16… (puissances de 2, pour la performance binaire) |
| PostgreSQL (hachage de partition) | Module premier pour les fonctions de hachage additives |
| Règle empirique | Taille premier = moins de collisions, mais accès binaire impossible |
Choisir la taille de sa table de hachage revient à choisir entre performance bitwise (puissances de 2) et qualité de distribution (premiers). Tester la primalité d'une valeur candidate prend < 1 ms pour n < 10⁶.
Domaine 3 — Théorie des nombres en classe et concours : lire un résultat de test comme un mathématicien
En terminale, BTS et classes préparatoires, la décomposition en facteurs premiers est l'outil de base pour calculer les PGCD, PPCM, l'indicatrice d'Euler φ(n), et l'ordre multiplicatif. Chaque composante du résultat de cet outil a une utilité directe dans ces calculs.
| n = 360 = 2³ × 3² × 5 | τ(360) = (3+1)(2+1)(1+1) = 24 diviseurs |
| φ(360) (Euler) | 360 × (1−1/2)(1−1/3)(1−1/5) = 96 |
| σ(360) (somme diviseurs) | (2⁴−1)/(2−1) × (3³−1)/(3−1) × (5²−1)/(5−1) = 1170 |
| PPCM(360, 840) | 840 = 2³×3×5×7 → PPCM = 2³×3²×5×7 = 2 520 |
| Sans décomposition | Ces calculs nécessitent plusieurs étapes manuelles — l'outil les donne en 0 ms |
Anatomie d'un nombre premier : ce que révèle chaque propriété affichée
Les résultats affichés par cet outil vont au-delà du simple verdict premier/composé. Chaque valeur calculée répond à une question arithmétique distincte :
τ(n) — le nombre de diviseurs
Pour n = p₁ᵃ¹ × p₂ᵃ² × … × pₖᵃᵏ, on a τ(n) = (a₁+1)(a₂+1)…(aₖ+1). Un premier p a toujours τ(p) = 2 (diviseurs : 1 et p). C'est une condition nécessaire mais non suffisante — τ(4) = 3, τ(9) = 3, mais 4 et 9 sont composés.
| n | Décomposition | τ(n) |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 30 | 2 × 3 × 5 | 8 |
| 360 | 2³ × 3² × 5 | 24 |
| 720720 | 2⁴×3²×5×7×11×13 | 240 |
σ(n) et la classification arithmétique
La somme des diviseurs propres (σ(n) − n) classe tout entier en trois catégories :
| Classification | Condition | Exemples |
|---|---|---|
| Parfait | σ(n) = 2n | 6, 28, 496, 8128 |
| Abondant | σ(n) > 2n | 12, 18, 20, 24… |
| Déficient | σ(n) < 2n | Tous les premiers, 1, 4, 8… |
Fait : tous les nombres premiers sont déficients (σ(p) = p+1 < 2p). Le plus petit nombre abondant impair est 945 = 3³ × 5 × 7.
Conjectures ouvertes sur les nombres premiers : ce que les mathématiciens ne savent pas encore en 2026
Les nombres premiers sont l'objet de questions fondamentales dont certaines résistent depuis des siècles. Comprendre ces conjectures, c'est comprendre pourquoi la théorie des nombres reste un domaine actif en 2026.
| Conjecture | Énoncé simplifié | État en 2026 | Lien avec nos résultats |
|---|---|---|---|
| Conjecture de Goldbach | Tout entier pair > 2 est somme de deux premiers | Non prouvée — vérifiée jusqu'à 4 × 10¹⁸ | Les deux premiers affichés dans la décomposition peuvent être la paire de Goldbach |
| Premiers jumeaux | Il existe une infinité de paires (p, p+2) premières | Non prouvée — Zhang (2013) : gaps bornés par 246 | L'écart avec les voisins premiers (affiché) identifie les paires jumelles |
| Hypothèse de Riemann | Tous les zéros non-triviaux de ζ(s) ont partie réelle 1/2 | Non prouvée — Problème du millénaire (1 M$) | Détermine la distribution des premiers — lie π(n) à √n |
| Premiers de Mersenne (2ᵖ−1) | Il en existe une infinité | Non prouvée — 52ᵉ connu trouvé en 2024 | Testez 2 147 483 647 = 2³¹−1 : premier de Mersenne M₃₁ |
| Premiers de Fermat (2^(2ⁿ)+1) | F₀…F₄ sont premiers, F₅ et au-delà composés ? | Tous les Fₙ testés (n > 4) sont composés — non prouvé général | F₅ = 4 294 967 297 = 641 × 6 700 417 — testez-le |
Distribution des nombres premiers : la densité qui décroît, mais jamais à zéro
Le théorème des nombres premiers (Hadamard, de la Vallée-Poussin, 1896) établit que le nombre de premiers inférieurs à n, noté π(n), est asymptotiquement équivalent à n / ln(n). Cette décroissance de densité est régulière en moyenne, mais cache des irrégularités locales importantes :
| Jusqu'à n | π(n) premiers | Densité | 1 premier tous les… |
|---|---|---|---|
| 100 | 25 | 25,0 % | 4 entiers |
| 1 000 | 168 | 16,8 % | 6 entiers |
| 10 000 | 1 229 | 12,3 % | 8 entiers |
| 100 000 | 9 592 | 9,6 % | 10 entiers |
| 1 000 000 | 78 498 | 7,8 % | 13 entiers |
| 10⁹ | 50 847 534 | 5,1 % | 20 entiers |
| 10¹² | 37 607 912 018 | 3,8 % | 27 entiers |
Lacunes primaires (prime gaps) : les déserts de composés
Entre deux premiers consécutifs, il peut exister de très grands intervalles entièrement composés. Ces lacunes sont imprévisibles localement :
| Région | Plus grand gap connu localement |
|---|---|
| Autour de 100 | 8 (entre 89 et 97) |
| Autour de 10 000 | 36 (entre 9 551 et 9 587) |
| Autour de 10⁶ | 148 (entre 492 113 et 492 227) |
| Autour de 10⁹ | 282 (entre 436 273 009 et…) |
| Record absolu connu | Gap de 1 510 entre deux premiers à ~10¹⁸ |
Application directe : les voisins premiers affichés par cet outil permettent de calculer immédiatement la lacune autour de n. Si vous testez un entier n et que le premier suivant est à n+2, vous avez trouvé une paire de premiers jumeaux — l'une des structures les plus rares et les plus étudiées de l'arithmétique.
Erreurs fréquentes et bonnes pratiques
Erreurs fréquentes
- Croire que 1 est un nombre premier — il n'a qu'un seul diviseur, pas deux
- Penser que tout impair est premier (9, 15, 21, 25 sont impairs et composés)
- Confondre « nombre premier » et « nombre impair premier » — 2 est le seul pair premier
- Utiliser un test probabiliste sans vérifier le nombre de tours (faux positifs possibles)
- Oublier que la décomposition est unique (théorème fondamental de l'arithmétique) — il n'y a pas d'ambiguïté
- Croire que les premiers de Mersenne (2ᵖ−1) sont toujours premiers — faux dès p = 11 : 2¹¹−1 = 2047 = 23 × 89
Bonnes pratiques
- Vérifier en multipliant les facteurs : le produit doit redonner n exactement
- Pour des nombres > 10¹³, préférer un test Miller-Rabin déterministe (bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
- Pour la crypto : toujours générer plusieurs candidats et tester la primalité, pas choisir le premier venu
- En algorithmique : précalculer un crible d'Ératosthène pour n < 10⁷ si on teste beaucoup de nombres
- Utiliser notre calculatrice PGCD avec les facteurs trouvés pour simplifier des fractions
- Combiner avec notre liste de nombres premiers pour identifier des patterns
Decision guide — Quel algorithme utiliser selon votre besoin ?
| Votre besoin | Algorithme recommandé | Pourquoi |
|---|---|---|
| Tester un nombre < 10⁶ (exercice scolaire) | Division d'essai jusqu'à √n | Implémentable à la main, résultat immédiat |
| Tester un nombre < 10¹³ (cet outil) | Roue mod 30 + division d'essai | Déterministe, < 500 ms dans le navigateur |
| Tester massivement des nombres < 10⁷ | Crible d'Ératosthène | O(n log log n) — le plus efficace en mémoire bornée |
| Tester un nombre entre 10¹³ et 10²⁴ | Miller-Rabin déterministe (12 bases fixes) | Certitude totale, millisecondes |
| Tester un nombre > 10²⁴ (cryptographie) | Miller-Rabin probabiliste (≥ 64 tours) + BPSW | Aucun faux positif connu du test BPSW |
| Prouver la primalité avec certificat | ECPP (courbes elliptiques) | Certificat vérifiable indépendamment — standard FIPS |
| Trouver le plus grand facteur premier | Factorisation rho de Pollard | O(n^(1/4)) — bien meilleur que la division d'essai pour grands n |
Calculatrices complémentaires
Le test de primalité s'inscrit dans l'arithmétique des entiers — voici les outils naturellement liés :
Liste de nombres premiers
Générer tous les premiers jusqu'à n par crible d'Ératosthène
Plus grand facteur commun (PGCD)
Utilise la décomposition en facteurs premiers pour simplifier
Plus petit multiple commun (PPCM)
Calcul direct depuis la décomposition en facteurs
Simplifier une fraction
La fraction est irréductible si PGCD(p,q) = 1 — vérifié via les facteurs
Équation du 2nd degré
Le discriminant peut révéler des facteurs premiers dans ses racines
Notation scientifique
Exprimer de très grands premiers (Mersenne) en notation compacte