6XC

Liste et vérification de nombres premiers

Listez tous les nombres premiers d'un intervalle (crible d'Ératosthène), ou vérifiez si un nombre est premier — résultats instantanés.

1 055 vues

Comment ça marche

L'outil bascule entre deux algorithmes différents, chacun adapté à une question différente. Le mode Liste trouve tous les nombres premiers jusqu'à une limite grâce au crible d'Ératosthène, l'un des plus anciens algorithmes encore utilisé quotidiennement (attribué au mathématicien grec Ératosthène, IIIe siècle av. J.-C.). En partant de 2, il élimine tous les multiples de 2 en tant que composés, puis passe au prochain nombre non marqué (3) et élimine tous ses multiples, puis au prochain nombre non marqué (5), et ainsi de suite. Tout ce qui reste non marqué une fois atteinte la racine carrée de la limite est premier. Petit exemple : pour cribler jusqu'à 30, on raye les multiples de 2 (4,6,8,…), puis les multiples de 3 (6,9,12,…, certains déjà rayés), puis les multiples de 5 (10,15,…) — puisque 5×5=25 ≤ 30 mais 7×7=49 > 30, on peut s'arrêter là ; ce qui reste — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — est la liste complète. Cela s'exécute en temps O(n log log n), ce qui signifie que l'algorithme reste rapide même lorsque l'intervalle atteint plusieurs centaines de milliers.

Le mode Vérification répond à une question différente — ce nombre précis est-il premier ? — en utilisant la division d'essai jusqu'à la racine carrée. Pour tester si n est premier, il suffit de vérifier les diviseurs de 2 jusqu'à √n. Le raisonnement : si n = a × b avec a et b tous deux supérieurs à √n, alors a × b serait supérieur à n, ce qui est impossible. Donc au moins l'un des deux facteurs doit être égal ou inférieur à √n, et il sera trouvé avant la fin de la boucle. Exemple : pour vérifier 97, il suffit de tester la divisibilité par 2, 3, 5, 7 (puisque 9² = 81 ≤ 97 mais 10² = 100 > 97) — aucun ne divise exactement, donc 97 est premier.

Ce qu'il faut savoir

Les deux modes existent car ils comportent des compromis différents : le crible est efficace pour produire de nombreux nombres premiers à la fois, mais gaspille mémoire et temps si vous ne vous intéressez qu'à un seul nombre proche d'une limite énorme ; la division d'essai est efficace pour une vérification unique mais bien trop lente si elle est répétée pour chaque nombre d'un grand intervalle, un par un. Choisir le bon outil pour la tâche est exactement la raison pour laquelle cet outil propose les deux.

  • 1 est exclu des nombres premiers par définition et par convention — il n'a qu'un seul diviseur, pas deux, ce qui briserait l'unicité de la factorisation en nombres premiers s'il était admis.
  • 2 est le seul nombre premier pair ; tout autre nombre pair est divisible par 2 et donc composé.
  • À mesure que les nombres grandissent, les nombres premiers deviennent en moyenne plus rares, mais n'arrêtent jamais d'apparaître — Euclide a prouvé il y a plus de deux mille ans qu'il en existe une infinité.

Questions fréquentes

Qu'est-ce qu'un nombre premier ?

Un nombre naturel supérieur à 1 possédant exactement deux diviseurs positifs : 1 et lui-même. 1 n'est pas premier car il n'a qu'un seul diviseur, et les nombres négatifs ne sont jamais considérés comme premiers ou composés.

Quel est l'intervalle maximal que je peux lister ?

Jusqu'à 1 000 000 — dans cet intervalle, le crible d'Ératosthène reste rapide (sa complexité en O(n log log n) croît très lentement) et votre navigateur reste réactif.

Pourquoi la division d'essai ne doit-elle vérifier que jusqu'à la racine carrée ?

Si un nombre n possède un diviseur supérieur à √n, celui-ci doit forcément être associé à un diviseur inférieur à √n (puisque leur produit est égal à n). Donc toute paire de facteurs comporte toujours au moins un membre égal ou inférieur à la racine carrée — vérifier plus loin est redondant.

Pourquoi ne pas utiliser aussi la division d'essai pour lister ?

Ce serait possible, mais bien plus lent : tester individuellement chaque nombre d'un intervalle jusqu'à sa propre racine carrée demande bien plus de travail répété que le crible, qui élimine les multiples de chaque nombre premier en un seul passage efficace sur tout l'intervalle.

Existe-t-il une infinité de nombres premiers ?

Oui — Euclide en a donné une preuve vers 300 av. J.-C. : supposez une liste finie de tous les nombres premiers, multipliez-les entre eux et ajoutez 1 ; le résultat n'est divisible par aucun nombre premier de la liste, donc soit il est lui-même un nouveau nombre premier, soit il a un facteur premier absent de la liste. Dans les deux cas, la liste était incomplète.

Commentaires

Pas encore de commentaires — soyez le premier à en écrire un !

Outils similaires

Calculatrice Calculatrice en ligne gratuite avec prise en charge du clavier : quatre opérations, pourcentages, parenthèses et historique. Lancer Calcul de pourcentage Calculez X % d'un nombre, quel pourcentage un nombre représente d'un autre, et l'augmentation ou la diminution en pourcentage. Lancer Calculateur de PGCD & PPCM Calculez le plus grand commun diviseur et le plus petit commun multiple de deux nombres ou plus, avec les étapes affichées. Lancer Calculateur de combinaisons et permutations Calculez les combinaisons C(n,r), les permutations P(n,r) et la factorielle n! avec des résultats exacts. Lancer