Vérificateur de Nombre Premier (avec factorisation)

Qu'est-ce qu'un nombre premier

Un nombre premier est un entier naturel supérieur à 1 qui n'a pas d'autre diviseur positif que 1 et lui-même. Les premiers premiers nombres : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Ce sont les « atomes » de l'arithmétique des entiers — tout entier ≥ 2 peut s'écrire de façon unique comme produit de nombres premiers (Théorème fondamental de l'arithmétique).

1 n'est pas premier par convention. 0 et les nombres négatifs ne sont pas premiers. 2 est le seul nombre premier pair — tout autre nombre pair est divisible par 2 et donc composé.

Comment le test fonctionne

Nous utilisons la division d'essai : tester la divisibilité par 2, puis 3, puis 5, 7, 11, … jusqu'à √n. Si aucun ne divise exactement, n est premier. Nous utilisons l'optimisation 6k±1 qui ne vérifie que les candidats de la forme 6k+1 ou 6k−1 (car tous les premiers > 3 sont de cette forme), réduisant le nombre de tests de 2/3.

La division d'essai est rapide pour n jusqu'à ~10^15 (moins d'une seconde). Au-delà, des tests avancés comme Miller-Rabin (probabiliste) ou AKS (déterministe) sont nécessaires. Nous limitons à 10^18 pour éviter que le navigateur ne se fige sur des entrées extrêmes.

Pourquoi les nombres premiers sont importants

Cryptographie : le chiffrement RSA multiplie deux nombres premiers d'environ 1 000 chiffres pour produire un nombre difficile à factoriser. La sécurité repose sur la difficulté de factoriser de grands nombres — un défi étudié depuis des millénaires.

Enseignement des mathématiques : la décomposition en facteurs premiers est fondamentale. Les concepts comme le PGCD, le PPCM, l'arithmétique modulaire, les fractions et la théorie des nombres s'appuient tous sur la structure des facteurs premiers.

Informatique : les tailles de tables de hachage, les générateurs de nombres aléatoires et de nombreux algorithmes utilisent des nombres premiers pour leurs propriétés de divisibilité distinctives.