Calculatrice de nombre premier

n est premier <=> d(n) = 2 ; previousPrime(97) = 97 ; nextPrime(97) = 97 ; nextPrime(1 000 000) = 1 000 003

n

L’entier testé — de 2 à 1 000 000. La borne basse est délibérée et non héritée : le premier précédent de 1 n’existe pas, donc une page qui accepterait 1 aurait une ligne qu’elle ne pourrait pas remplir honnêtement. La question de savoir si 1 est premier relève de la définition et reçoit sa réponse dans les questions plus bas plutôt que dans la calculatrice

d(n)

Le nombre de diviseurs positifs, qui est la première ligne du résultat et la seule preuve sur laquelle repose le verdict. d(n) = 2 signifie qu’exactement deux nombres le divisent, ce qui est la définition d’un nombre premier. Ce compte vient de la routine d’arithmétique partagée, c’est donc la même valeur que la page des facteurs et celle de la décomposition en facteurs premiers rapportent pour la même entrée

d(n) = 2

Le test lui-même, énoncé sous forme d’équation. C’est une équivalence et non une approximation : un nombre est premier si et seulement s’il a exactement deux diviseurs. Pour 97 les diviseurs sont 1 et 97, le compte vaut donc 2 et la pastille affiche premier. Pour 100 ce sont 1, 2, 4, 5, 10, 20, 25, 50 et 100, le compte vaut donc 9 et la pastille affiche composé

previousPrime(n)

Le plus grand nombre premier inférieur ou égal à n. La borne haute est incluse, donc quand n est premier la réponse est n lui-même. Pour 100 la réponse est 97 ; pour 25 c’est 23 ; pour 97 c’est 97. L’intervalle est fermé parce que l’alternative exigerait une règle pour ce qu’il faut imprimer quand n est déjà premier, et une ligne vide dans un panneau de résultat se lit comme une panne plutôt que comme un fait

nextPrime(n)

Le plus petit nombre premier supérieur ou égal à n, avec la même règle inclusive en bas. Pour 25 c’est 29, pour 100 c’est 101, et pour 97 c’est 97. Celui-ci peut sortir de la plage de l’entrée : nextPrime(1 000 000) vaut 1 000 003, un nombre premier plus grand que tout ce que la page accepte, et il est rapporté comme réponse plutôt que traité comme hors limites

1e6 à 1e6 + 100

Le voisinage du plafond d’entrée, et la raison pour laquelle un test distinct y est nécessaire. Les nombres premiers proches d’un million sont 999 983 et 1 000 003, donc la recherche lancée depuis 1 000 000 doit regarder au-delà d’un million dans une direction. La routine qui compte les diviseurs refuse les arguments supérieurs à un million et lèverait une erreur, la recherche de voisins utilise donc son propre test, qui n’a pas cette limite — et les deux doivent tomber d’accord partout où ils se recouvrent, ce que vérifient les lignes premières des exemples

Choisir un module est la raison la plus pratique de vouloir un nombre premier proche d’un nombre que l’on a déjà choisi. Le nombre d’emplacements d’une table de hachage est habituellement pris premier, parce qu’un module premier répartit les clés qui partagent un facteur au lieu de les laisser entrer en collision ; une table dimensionnée 1 000 envoie tous les multiples de 25 dans les mêmes quelques emplacements, ce qu’une table dimensionnée 997 ne fait pas. Le même réflexe s’applique en cryptographie, où les clés sont construites à partir de nombres premiers grands et éloignés les uns des autres. Vérifier si un nombre est premier tranche aussi rapidement des questions de divisibilité : si un nombre n’a aucun diviseur premier jusqu’à sa racine carrée, il n’en a aucun du tout, et la pastille répond en une étape au lieu d’un balayage. Certains problèmes ne portent que sur la primalité — les nombres premiers jumeaux, les écarts entre nombres premiers consécutifs, et la question de savoir si un nombre donné est le produit de deux nombres premiers. Quand la question se révèle porter sur les facteurs eux-mêmes, la page de la décomposition casse le nombre en nombres premiers et constitue l’arrêt suivant naturel ; quand elle porte sur les nombres qui divisent le vôtre, la page des facteurs les liste tous ; et quand le nombre testé n’est pas premier et que vous voulez savoir de quoi il est fait, le compte de diviseurs de cette page est le premier indice plutôt que la réponse complète.

1. Un nombre premier : 97

   1. On teste les diviseurs de 97 : 2 ne le divise pas, et 3, 5, 7 ni 11 non plus
   2. On s’arrête à la racine carrée : 10 × 10 = 100 dépasse déjà 97, il ne reste donc rien à tester
   3. Les seuls diviseurs sont 1 et 97, le compte vaut donc 2 et le nombre est premier
   4. Le premier précédent est 97 lui-même, parce que 97 est déjà premier et que la recherche est inclusive
   5. Le premier suivant vaut 97 lui aussi, pour la même raison

   La saisie par défaut, et l’illustration la plus nette de la règle inclusive. Les deux voisins reviennent égaux au nombre lui-même, ce qui donne d’abord l’impression que ces lignes n’ont rien fait. Elles ont fait quelque chose : le plus grand nombre premier qui ne dépasse pas 97 est 97, et le plus petit qui ne lui est pas inférieur est 97 également. L’alternative — une inégalité stricte — laisserait ces deux lignes sans rien à imprimer précisément sur les entrées où la page est la plus sûre d’elle, et une ligne vide dans un panneau de résultat se lit comme une erreur. C’est aussi le cas où les deux tests indépendants de la page se rencontrent : le compte de diviseurs dit 2, et la recherche de voisins confirme que 97 est premier, et ils y arrivent par du code différent.

2. Un nombre composé : 100

   1. 100 est pair, donc 2 le divise ; il se termine par 00, donc 4, 5, 10, 20, 25 et 50 le divisent aussi
   2. Les diviseurs sont 1, 2, 4, 5, 10, 20, 25, 50 et 100 — neuf en tout
   3. Neuf est plus que deux, donc la pastille affiche composé et non premier
   4. Le plus grand nombre premier inférieur ou égal à 100 est 97 ; le plus petit supérieur ou égal est 101
   5. Les deux voisins sont juste à côté du nombre, ce à quoi ressemble un composé au milieu d’un écart

   Le cas qui montre les voisins en train de vraiment travailler. Quand un nombre est composé, les deux lignes de voisins sont la sortie utile, parce qu’elles répondent à la question que le lecteur se pose ensuite : si ce n’est pas ce nombre, lequel alors ? Quatre-vingt-dix-sept et cent un sont les nombres premiers les plus proches, et 100 se tient entre eux. Le compte de neuf mérite aussi un coup d’œil — il est impair, ce qui arrive exactement quand le nombre est un carré parfait, et 100 est le carré de 10. Un seul regard sur le compte vous dit donc déjà quelque chose sur la forme du nombre, avant toute factorisation.

3. Un nombre juste après un nombre premier : 25

   1. Les diviseurs de 25 sont 1, 5 et 25 — trois en tout, parce que 5 s’apparie avec lui-même
   2. Trois est plus que deux, donc 25 est composé
   3. On descend depuis 25 : 24, 23 — 23 est premier, c’est donc le premier précédent
   4. On monte depuis 25 : 26, 27, 28, 29 — 29 est premier, c’est donc le premier suivant
   5. L’écart ici vaut six en tout : 23 et 29 encadrent 25

   Un carré parfait, ce qui explique le nombre impair de diviseurs, et un cas où les deux voisins sont à des distances visiblement différentes — deux en dessous et quatre au-dessus. Le compte de trois montre aussi pourquoi deux est le bon seuil plutôt qu’un compte de facteurs premiers : 25 n’a qu’un seul facteur premier, 5, mais il n’est pas premier, et le nombre de diviseurs l’attrape sans avoir besoin de regarder la décomposition du tout.

L’entrée doit être un entier de 2 à 1 000 000. Zéro et un sont refusés, et un l’est pour une raison différente de zéro : c’est une question de définition plutôt qu’un nombre hors plage, et le premier précédent de 1 n’existe pas. Les nombres négatifs sont refusés — la primalité est une propriété des entiers supérieurs à 1, et s’il existe une convention de nombres premiers négatifs dans certaines branches des mathématiques, cette page n’en adopte aucune. Les nombres décimaux sont refusés plutôt qu’arrondis. Le plafond d’un million ne s’applique qu’à l’entrée ; les deux lignes de voisins peuvent légitimement rapporter un nombre premier au-delà, et le nombre premier qui suit un million est 1 000 003, qui est rapporté au lieu d’être refusé. Le test qui sous-tend le verdict est la division par essais jusqu’à la racine carrée, instantanée à cette taille et sans espoir sur un nombre à vingt chiffres, et cette frontière est une propriété du problème plutôt que de cette implémentation. La page rapporte trois nombres et une pastille : elle ne liste pas les diviseurs eux-mêmes, ne factorise pas un nombre composé, et teste un nombre à la fois plutôt qu’une plage. Les tableaux de référence plus bas sont des lignes figées et non une réponse à votre saisie. Enfin, un nombre premier est rapporté comme son propre précédent et son propre suivant, ce qui est un choix délibéré d’intervalle fermé et non deux lignes qui n’auraient rien trouvé.

1 est-il un nombre premier ?

Non, et ce n’est pas un nombre composé non plus. Un nombre premier se définit comme un entier supérieur à 1 ayant exactement deux diviseurs positifs, et 1 n’en a qu’un seul : il échoue donc à la définition sur les deux tableaux. C’est un choix délibéré et non un oubli : si l’on comptait 1 comme premier, l’énoncé selon lequel tout nombre a exactement une décomposition en facteurs premiers cesserait d’être vrai, puisqu’on pourrait multiplier une décomposition par 1 autant de fois qu’on le voudrait. C’est l’exclusion de 1 qui garde ce théorème propre. Comme il s’agit de définition et non d’arithmétique, la page n’accepte pas 1 en entrée — la réponse se trouve ici.

Pourquoi le premier précédent et le premier suivant valent-ils tous les deux le nombre lui-même ?

Parce que les deux recherches sont inclusives. Le premier précédent est le plus grand nombre premier qui ne dépasse pas votre nombre, et le premier suivant est le plus petit qui ne lui est pas inférieur. Quand le nombre est déjà premier, il satisfait aux deux descriptions, donc les deux lignes le rapportent. L’alternative serait une inégalité stricte, et une entrée première laisserait alors deux lignes sans rien à imprimer. Une ligne vide dans un panneau de résultat se lit comme une anomalie, et la page serait incapable de répondre au seul cas où elle est la plus sûre d’elle. La même convention apparaît dans les arrondis, où un nombre déjà à la précision visée revient inchangé.

Pourquoi le premier suivant peut-il dépasser un million alors que l’entrée ne le peut pas ?

Parce que le plafond est une limite sur ce que vous pouvez demander, et non sur ce que la réponse peut valoir. Le nombre premier qui suit 1 000 000 est 1 000 003, et refuser de l’imprimer reviendrait à refuser de répondre à une question parfaitement bien posée sur une entrée que la page a acceptée. La recherche de voisins tourne donc sur son propre test, sans borne supérieure, tandis que le compte de diviseurs continue d’utiliser la routine partagée qui ne couvre que la plage. Cela signifie bien que deux morceaux de logique décident tous les deux si un nombre est premier — l’un borné, l’autre pas — et ils sont tenus de tomber d’accord partout où ils se recouvrent, ce que vérifie l’exemple de 97 : le compte dit 2, et la recherche de voisins confirme que 97 est premier.

À quoi sert vraiment un nombre premier ?

À dimensionner des choses, le plus souvent. Les tables de hachage reçoivent habituellement un nombre premier d’emplacements, parce qu’un module premier disperse les clés qui partagent un facteur — une table de 1 000 emplacements envoie tous les multiples de 25 dans les mêmes quelques positions, ce qu’une table de 997 emplacements ne fait pas. Le même raisonnement vaut partout où un compteur reboucle : une longueur de cycle première évite de résonner avec des motifs réguliers présents dans les données. La cryptographie est l’autre grand usage, où les clés sont construites à partir de nombres premiers à la fois très grands et éloignés, et où la sécurité repose sur la difficulté de refactoriser leur produit en les deux nombres premiers d’origine. Les usages plus modestes sont partout : vérifier une affirmation de divisibilité, tester si un nombre est le produit de deux nombres premiers, et les problèmes classiques sur les nombres premiers jumeaux et les écarts entre nombres premiers consécutifs.

Comment la page décide-t-elle, et avec quelle certitude ?

En comptant les diviseurs, ce qui est exact et non probabiliste. Un nombre est premier si et seulement s’il a exactement deux diviseurs positifs, donc le compte tranche la question sans possibilité de réponse fausse, et sans avoir à faire confiance à un test qui pourrait être trompé. Le comptage se fait par la division par essais, en testant les diviseurs jusqu’à la racine carrée, et c’est pourquoi un million est le plafond : au-delà, la méthode devient lente plutôt que peu fiable. Pour des nombres bien plus grands, les méthodes exactes deviennent réellement impraticables et on utilise des tests probabilistes, mais à cette taille il n’y a aucune raison d’accepter moins que la certitude, et la page ne le fait pas.

Pourquoi afficher le nombre de diviseurs plutôt que le seul verdict ?

Parce que le compte est la raison du verdict, et l’afficher garantit que les deux ne peuvent jamais se contredire — la pastille n’est pas un second calcul mais une lecture du nombre imprimé juste à côté. Il est aussi utile en lui-même. Un compte impair signifie que le nombre est un carré parfait, puisque la racine carrée s’apparie avec elle-même plutôt qu’avec un autre diviseur. Un compte de 2 est la définition d’un nombre premier. Un compte grand par rapport à la taille du nombre dit qu’il a beaucoup de petits facteurs, ce qui est le genre de nombre qui récolte des diviseurs vite. Et cela relie la page aux autres : celle de la décomposition en facteurs premiers rapporte le même nombre de diviseurs pour la même entrée, en le calculant à partir des exposants, si bien que les deux pages se contrôlent l’une l’autre.

• Prime Number — the definition, the divisor-count test, and why 1 is excluded by it — Wolfram MathWorld (United States)
• Prime Gaps — the distances between consecutive primes, and what the neighbourhood of a million looks like — Wolfram MathWorld (United States)
• Composite Number — the complement of the primes, and why 1 belongs to neither group — Wolfram MathWorld (United States)
• Nombre premier — la définition francophone, le critère du nombre de diviseurs, l’exclusion de 1 et la répartition des nombres premiers — Wikipédia en français