Vérificateur de nombre premier

Comment vérifier si un nombre est premier

1. Saisissez un Nombre entier. Les expressions sont acceptées : 2^61-1, 10^12+39, 20!+1 ou 3711.
2. La réponse s’affiche pendant la saisie ; cliquez sur Vérifier pour laisser plus de temps à la décomposition d’un nombre difficile.
3. Lisez le verdict, la Décomposition en facteurs premiers, le Nombre de diviseurs, le Nombre premier précédent et le Nombre premier suivant. Le panneau Justification explique comment la réponse a été obtenue, et Copier la décomposition copie le produit de facteurs premiers.
4. Pour obtenir une liste, remplissez De et À dans la partie Nombres premiers dans un intervalle, puis cliquez sur Lister les nombres premiers.

Les nombres jusqu’à 2048 bits (environ 617 chiffres) sont acceptés, et tout le calcul se fait dans votre navigateur.

Qu’est-ce qu’un nombre premier ?

Un nombre premier est un entier supérieur à 1 qui n’a que deux diviseurs : 1 et lui-même. 2, 3, 5, 7, 11, 13… Un nombre qui a d’autres diviseurs est composé, et il s’écrit d’une seule façon comme produit de nombres premiers : c’est sa décomposition en facteurs premiers (360 = 2³ × 3² × 5). 0 et 1 ne sont ni premiers ni composés, et 2 est le seul nombre premier pair.

Le nombre de diviseurs se déduit de la décomposition : on ajoute 1 à chaque exposant et on multiplie. 360 = 2³ × 3² × 5 a (3 + 1)(2 + 1)(1 + 1) = 24 diviseurs. Un nombre premier en a toujours exactement 2.

Comment fonctionne le test

• Petits nombres (moins d’un million) : on essaie de diviser par chaque nombre premier jusqu’à la racine carrée. Si aucun ne divise le nombre, il est premier. Inutile d’aller plus loin : un nombre composé a toujours un facteur inférieur ou égal à sa racine carrée.
• Grands nombres : on divise d’abord par tous les nombres premiers inférieurs à 1000, puis on applique le test de Miller-Rabin. Avec les 13 bases 2, 3, 5… 41, ce test est prouvé exact pour tout nombre inférieur à 3,3 × 10²⁴, ce qui couvre tous les entiers de 64 bits. La réponse est alors certaine.
• Au-delà de 3,3 × 10²⁴, 25 bases sont utilisées et un nombre qui les passe toutes est déclaré premier probable. La probabilité d’erreur est inférieure à 1 sur 10¹⁵, mais ce n’est pas une preuve mathématique. Si le test échoue, le nombre est à coup sûr composé.

Comment les nombres sont décomposés

Les petits facteurs sont trouvés par divisions successives. Les parties composées plus grandes sont scindées par l’algorithme rho de Pollard (variante de Brent), qui trouve des facteurs d’une dizaine de chiffres en une fraction de seconde. Les nombres plus difficiles, comme le produit de deux nombres premiers de 15 chiffres ou plus, peuvent demander bien plus longtemps : la décomposition s’arrête donc après quelques secondes. Le dernier facteur est alors signalé comme composé mais non décomposé, et un nouveau clic sur Vérifier lui laisse plus de temps.

Nombres premiers dans un intervalle

La liste utilise un crible d’Ératosthène segmenté, qui raye les multiples de chaque nombre premier. L’intervalle peut contenir jusqu’à 1 000 000 de nombres, avec une borne supérieure jusqu’à 10¹². Le décompte porte sur tout l’intervalle et les 2000 premiers nombres premiers sont affichés. Il y a par exemple 25 nombres premiers entre 1 et 100, et 78 498 en dessous d’un million.