Aller au contenu
OneKitly

Prouver qu'un million est premier demande mille divisions, non un million

Publié le 16/11/2026 · 3 min de lecture · Calculateurs du quotidien

Lena Hoffmann

Lena Hoffmann — Rédactrice Sciences & Éducation chez OneKitly

Mathématiques · Physique

Vérifié à partir de 2 sources

Voir le profil →
En bref

Pour tester si un nombre a un facteur, il n'est jamais nécessaire de regarder au-delà de sa racine carrée. Si un nombre se scinde en deux facteurs, l'un est au plus égal à la racine et l'autre au moins égal : ne rien trouver de petit signifie donc qu'il n'y a rien du tout. Tester 1 000 003 ne demande donc des divisions d'essai que jusqu'à 1000, et il leur survit toutes : il est premier. Son voisin 1 000 001 tombe vite, car 101 le divise exactement, laissant 9901. La racine carrée est ce qui transforme une recherche impossible en travail d'un après-midi, et c'est la première chose que découvre quiconque écrit un test de primalité.

Publicité

1 000 003 est premier et la preuve s'arrête à 1000, sa racine carrée. 1 000 001 ne l'est pas, et la recherche s'achève au troisième essai : 101 le divise.

Seuls les premiers valent d'être essayés

Diviser par 4 est peine perdue si 2 a déjà échoué : la liste des candidats n'est pas les mille nombres sous la racine mais les 168 premiers qui s'y trouvent. Cela seul divise le travail par six, et sauter les pairs et les multiples de trois attrape presque gratuitement l'essentiel du reste. L'implémentation classique teste 2, puis 3, puis tout nombre de la forme « à un de part et d'autre d'un multiple de six », ce qui couvre tous les premiers possibles en n'essayant qu'un tiers des entiers.

Pourquoi l'astuce cesse d'aider

Diviser par deux le nombre de chiffres semble énorme jusqu'à ce que le nombre soit long. La racine carrée d'un nombre de 600 chiffres en a encore 300 : les divisions d'essai sur les clés de la cryptographie moderne exigeraient plus d'opérations qu'il n'y a d'atomes dans l'univers observable. Les vrais tests de primalité abandonnent donc la division et emploient des tests probabilistes dont la probabilité d'erreur peut être poussée sous n'importe quel seuil. Ces tests prouvent bien plus facilement qu'un nombre est composé qu'ils n'en exhibent un facteur, et c'est exactement l'asymétrie sur laquelle repose la sécurité.

Travail nécessaire pour tester un nombre par divisions d'essai
NombreDivisions à essayerRésultat
1 000 0013 avant l'échec101 × 9901
1 000 003168 premiers jusqu'à 1000Premier
Un nombre de 600 chiffresPlus que d'atomes dans l'universInutilisable
Vérificateur de nombre premierVérifie si un nombre est premier et trouve son plus petit diviseur.Essayer l'outil →
Publicité

Questions fréquentes

Pourquoi 1 n'est-il pas premier ?
Par décision, pour garder l'unicité de la factorisation. Si 1 comptait, 12 pourrait s'écrire 2×2×3, ou 1×2×2×3, ou 1×1×2×2×3, et l'énoncé selon lequel tout nombre a exactement une factorisation première demanderait une clause d'exception. Les tables du XIXe siècle listaient bien 1 comme premier, et la convention a changé parce que chaque théorème devenait plus propre sans lui. Les définitions en mathématiques se choisissent pour leurs conséquences plutôt qu'elles ne se découvrent, et voici le plus clair des petits exemples.
Comment tester un nombre à la main ?
Prenez la racine carrée, arrondissez au-dessus, et divisez par tous les premiers jusque-là. Sous dix mille, cela fait au plus 25 divisions, dont l'essentiel se règle instantanément : les pairs échouent sur 2, les sommes de chiffres divisibles par trois échouent sur 3, tout ce qui finit par 0 ou 5 échoue sur 5. Ce qui survit pour être testé sérieusement forme une courte liste. Au-delà du million, la méthode devient fastidieuse plutôt que difficile, et c'est exactement le moment de la confier à une machine.

Articles qui pourraient t'intéresser

Tous les guides →

Outils similaires

Sources

Tu as repéré une erreur dans cet article ?