Le50enligneBIS
> Calculettes "maison" > Maths > Divers > Nombres premiers

Nombres premiers

 [1] [2] [3] [4]


calculettes

Calculette_Chercher_les_nombres_premiers
Calculette_Crible_d’Ératosthène
Calculette_Décomposer_en_nombres_premiers
Calculette_nombres_de_Mersenne
fermer la calculette en popup

nb : π ( s ) est est la quantité totale de nombres premiers situés sous le seuil s (c’est-à-dire dans l’intervalle d’entiers [ 0 , s ] .

ainsi π ( 1000 ) = 168 ce qui signifie qu’il y a 168 nombres entiers entre 0 et 1000 qui sont premiers. Donc uniquement divisibles par eux-même ou par 1 (non premier).

π ( 7919 ) = 1000 donc les 1000 premiers nombres premiers sont compris entre 0 et 7919.

jouez avec la première calculette ! sur la deuxième, par exemple, décomposez 2147483647 qui est un nombre de Mersenne premier (2 ^ 31 – 1) que vous pouvez trouver sur la troisième.

Nos PC sont puissants mais ne peuvent pas rivaliser avec les gros calculateurs donc doucement sur le seuil (100 000 ça passe facile pour trouver le 9592 nombre premiers) pour la première calculette.

nombres premiers

Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même). Ainsi, 1 n’est pas premier car il n’a qu’un seul diviseur entier positif ; 0 non plus car il est divisible par tous les entiers positifs. Par opposition, un produit de deux entiers strictement supérieurs à 1 est dit composé. Par exemple 6 = 2 × 3 est composé, tout comme 12 = 3 × 4 ou 2 × 6, mais 11 est premier car 1 et 11 sont les seuls diviseurs de 11.

Les nombres 0 et 1 ne sont ni premiers ni composés. Certains mathématiciens considéraient autrefois (jusqu’au 19e siècle) 1 comme un nombre premier, mais durant le début du 20e siècle, un consensus exclut définitivement sa primalité.

Les vingt-cinq nombres premiers inférieurs à 100 sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 et 97.

explication visuelle

on cherche avec un nombre n de billes à former un rectangle

O O O O O O O O O O
O O O O O O O O O O
O O O O O O O O O O
O O O O O O O O O O

ici avec 40 billes on peux par exemple faire un rectangle de 10 x 4

ou 5 x 8

O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O

40 n’est donc pas premier car 40 = 5 x 8 = 23 x 5

Si on ne peux pas faire un rectangle

n=17

O O O O O O O O
O O O O O O O O
O

alors le nombre n’est pas premier.

par contre :

n=18

O O O O O O O O
O O O O O O O O
O O

peux former un rectangle, par exemple 3 x 6

O O O O O O
O O O O O O
O O O O O O

Il serait trop coûteux en billes ;-) de vérifier avec 22 091, 9 576 890 767 ou encore ce géant :
95 647 806 479 275 528 135 733 781 266 203 904 794 419 563 064 407.
qui sont des nombres premiers.

nombres de Mersenne

Nombres premiers de Mersenne

Marin Mersenne (1588-1648).

Les nombres premiers de la forme : M p = 2p − 1 où p est alors nécessairement aussi premier, sont appelés nombres premiers de Mersenne. Les grands nombres premiers sont souvent recherchés sous cette forme car il existe un test efficace, le test de primalité de Lucas-Lehmer, pour déterminer si un tel nombre est premier ou non.

Liste des 20 premiers nombres de Mersenne, certains premiers, d’autres pas
rang2^p - 1 premier ?
1 1  - 
2 3 premier
3 7 premier
4 15 composé
5 31 premier
6 63 composé
7 127 premier
8 255 composé
9 511 composé
10 1023 composé
11 2047 composé
12 4095 composé
13 8191 premier
14 16383 composé
15 32767 composé
16 65535 composé
17 131071 premier
18 262143 composé
19 524287 premier
20 1048575 composé
Les 20 premiers nombres de Mersenne qui sont premiers sont :
  • 2 ^ 2 – 1 = 3
  • 2 ^ 3 – 1 = 7
  • 2 ^ 5 – 1 = 31
  • 2 ^ 7 – 1 = 127
  • 2 ^ 13 – 1 = 8191
  • 2 ^ 17 – 1 = 131071
  • 2 ^ 19 – 1 = 524287
  • 2 ^ 31 – 1 = 2147483647
  • 2 ^ 61 – 1
  • 2 ^ 89 – 1
  • 2 ^ 107 – 1
  • 2 ^ 127 – 1
  • 2 ^ 521 – 1
  • 2 ^ 607 – 1
  • 2 ^ 1279 – 1
  • 2 ^ 2203 – 1
  • 2 ^ 2281 – 1
  • 2 ^ 3217 – 1
  • 2 ^ 4253 – 1
  • 2 ^ 4423 – 1 = 2,8554254222827961390156356610216e+1331

Au délà de 2^31, les résultats en javascript sont faux (explication plus bas).

Entre 2008 et 2012, le plus grand nombre premier connu était M43 112 609 = 243 112 609 – 1, qui comporte 12 978 189 chiffres en écriture décimale. Il s’agit (chronologiquement) du 45e nombre premier de Mersenne connu et sa découverte a été annoncée le 23 août 2008 par le GIMPS [5]. Un 46e nombre premier de Mersenne, 237 156 667 – 1, inférieur au précédent, a été découvert deux semaines plus tard ; le 12 avril 2009 était découvert, par le même projet GIMPS, un 47e nombre premier de Mersenne, 242 643 801 – 1, lui aussi inférieur au premier cité.

Ce record a été battu (toujours par le GIMPS) par la preuve de la primalité de M57 885 161 = 257 885 161 – 1 (en janvier 2013) puis à nouveau, le 7 janvier 2016, par celle de M74 207 281, et enfin, le 3 janvier 2018, par celle de M77 232 917. [6]

test de Lucas-Lehmer

Le test de Lucas-Lehmer

Ce test de primalité (tester si un nombre de Mersenne est premier) n’est pas si simple mais résumé ici dans un pseudo code très clair.


// Determine if Mp = 2p − 1 is prime
Lucas–Lehmer(p)
var s = 4
var M = 2p − 1
repeat p − 2 times :
s = ((s × s) − 2) mod M
if s = 0 return PRIME else return COMPOSITE

Il est simple de l’écrire en n’importe quel language tel que le javascript. Toutefois pour les grands nombres, le résultat sera faussé par la conversion en puissance de 10 avec un arrondi. On perd donc assez vite les digits d’un nombre. exemple : 7.20575940379279e+16

Crible d’Ératosthène

Crible d'Ératosthène

voir ICI

Une simple et élégante méthode de recherche des nombres premiers de l’intervalle [1,n] des entiers naturels sur ordinateur est celle du crible d’Ératosthène [7] :

On part d’une évidence : un diviseur propre d’un nombre n (c’est à dire distinct de ce nombre) est inférieur à n.

  • Commençant à 2, on supprime tous les multiples de 2.
  • L’entier 3 n’a pas été supprimé et il ne peut être multiple des entiers qui le précèdent, sinon on l’aurait supprimé ; il est donc premier : supprimons alors tous les multiples de 3.
  • L’entier 5 n’a pas été supprimé, il est donc premier. Et ainsi de suite.

Sans être programmeur, vous pouvez le faire sur un tableau de 10 x 10 et vous trouverez une fois barré tous les nombres premiers inférieurs à 100.

La quatrième calculette trouve fort heureusement les même résultats que la première mais est plus lente avec cet algorithme.

Notes

[1]

La molécule la plus utilisée par les développeurs pour écrire des trucs pareils à point d’heure, c’est : C8H10N4O2, plus connue sous le nom de "caféïne"

[2] le chiffre UN (1) est abusivement appelé nombre premier, il ne l’est pas.

[3] L’effet démo, mon neveu en visite ... essaye et tape ton année de naissance ...2003 .. ça sert à rien ton truc (sur la deuxième calculette)

[4] assez vite j’ai trouvé 2777777945607127 comme nombre premier, vous devriez trouver plus haut asser rapidement.
soit :
Deux mille sept cent soixante-dix-sept billions sept cent soixante-dix-sept milliards neuf cent quarante-cinq millions six cent sept mille cent vingt-sept
vous devriez trouver mieux, j’ai mis deux minutes (au pif) ;-P

[5] GIMPS : Great Internet Mersenne Prime Search

[6] Le nouveau nombre premier découvert à la toute fin de 2017 correspond donc à M77232917. Il a 23 249 425 chiffres – près d’un million de chiffres de plus que le nombre premier record précédent. Un Document word écrit en Times New Roman, avec une taille de police de 10 et les marges classiques, représenterait 3845 pages.

La date officielle de la découverte est le jour où un homme déclare le résultat. Ceci est en accord avec la tradition  : M4253 est réputé ne jamais avoir été le plus grand nombre premier connu parce qu’en 1961, le mathématicien américain Alexander Hurwitz avait lu la sortie d’imprimante à partir de la fin et trouva M4423 quelques secondes avant de voir que M4253 était aussi premier. De même, le nombre de Mersenne précédent a vécu une histoire compliquée  : l’ordinateur a signalé le résultat au serveur le 17 Septembre 2015 mais un bug a empêché l’envoi de l’e-mail. Le nouveau nombre premier est resté inaperçu jusqu’à la maintenance de la base, c’est-à-dire le 7 janvier 2016.

277232917-1 est le 50e nombre de Mersenne premier et si le défi de la découverte du 51e vous tente, vous pouvez trouver un programme de vérification ici et peut être même gagner les 3000 dollars proposés à l’heureux(se) gagnant-e. (Attention Jonathan Pace, qui a le premier découvert ce nombre, y travaille depuis quatorze ans)

[7] Ératosthène est un grand astronome, géographe, mathématicien, philosophe et poète grec, né vers -276 à Cyrène, mort vers -194 à Alexandrie. Il était à la tête de la bibliothèque d’Alexandrie au temps du pharaon Ptolémée III ( 245 avant Jésus-Christ). Selon la légende, il serait devenu aveugle en vieillissant. Ne pouvant plus étudier les étoiles, il se serait laissé mourir de faim.

Il a créé de nombreux outils mathématiques. Sa méthode pour l’étude des nombres premiers est restée célèbre sous le nom de Crible d’Eratosthène. Il réalisa de nombreux travaux en astronomie en créant un premier observatoire astronomique qui lui permit de réaliser des tables d’éclipses pour prédire leur(s) apparition(s). Il créa également un catalogue astronomique recensant près de 675 étoiles. Toutes ses observations du ciel lui ont permis de déterminer que la Terre était inclinée. Il est également connu pour avoir dessiné une des premières cartes du monde connu au IIIe siècle avant Jésus-Christ.

Ses travaux les plus connus portent sur la circonférence de la Terre. Ératosthène est connu pour en avoir, le premier, donné une mesure fiable. En utilisant certaines propriétés géométriques des angles alternes-internes et en se basant sur l’observation des ombres projetées à deux endroits différents, il est parvenu à l’estimer à 39 375 km, les mesures actuelles donnent 40 075,02 km (Il ne se trompa que de 700,02 km) !