Vérifier si un nombre est premier et trouver tous les premiers dans une plage
Un nombre premier est un entier naturel supérieur à 1 qui n'a pas de diviseurs positifs autres que 1 et lui-même. 2, 3, 5, 7, 11, 13... sont les premiers nombres premiers. Le théorème fondamental de l'arithmétique stipule que tout entier supérieur à 1 peut s'exprimer de façon unique comme produit de nombres premiers.
Cet outil vérifie si un nombre est premier, trouve sa décomposition en facteurs premiers s'il est composite, et liste les nombres premiers dans une plage donnée. Les nombres premiers sont au cœur de la cryptographie moderne — RSA repose sur la difficulté de factoriser de grands nombres.
Pour les petits nombres (<10⁶) : division d'essai jusqu'à √n. Pour les nombres moyens : Miller-Rabin déterministe. Pour les très grands nombres : Miller-Rabin probabiliste. AKS (2002) a été prouvé polynomial.
Oui. Euclide l'a prouvé vers 300 av. J.-C. : supposons une liste finie de premiers, multiplions-les tous et ajoutons 1 — ce nombre est premier ou divisible par un premier non listé. Contradiction.
Algorithme pour trouver tous les premiers jusqu'à une limite n. Marquer tous les multiples de chaque premier. Les nombres non marqués restants sont premiers. Complexité : O(n log log n).
Un nombre premier de la forme 2ⁿ − 1. Exemples : 3, 7, 31, 127. GIMPS coordonne l'informatique distribuée pour trouver de nouveaux nombres premiers de Mersenne.
Calculateur de pourcentage · Calculateur d'âge · Différence de dates · Calculatrice scientifique · Calculateur d'IMC · Générateur Fibonacci