Un nombre \(n\) est premier s'il ne possède que deux diviseurs : 1 et lui-même. Il existe plusieurs manières de savoir si un nombre \(n\) est premier ou non : la plus simple est de tester chaque nombre dans \(⟦2, n⟦\) pour voir si ce nombre est un diviseur de \(n\). En réalité, il suffit juste de tester les nombres premiers dans \(⟦2,\lfloor\sqrt{n}\rfloor⟧\). C'est la méthode qu'utilise le crible d'Erathostène (le même que celui qui a calculé le rayon de la Terre).
On suppose déjà connaître tous les nombres premiers entre 1 et 10 : 2, 3, 5 et 7. On souhaite maintenant déterminer rapidement tous les nombres premiers jusqu'à 100. Le crible d'Erathostène fonctionne en éliminant les candidats au statut de nombre premier divisibles par 2 (c'est-à-dire un nombre sur 2 à partir de 4), puis de 3, de 5 ... jusqu'à \(\lfloor\sqrt{n}\rfloor\), ici 10.
Les nombres premiers sont indiqués en vert.
Il existe une infinité de nombres premiers. Cependant, plus on cherche dans les grands nombres, moins il y en a.
Le nombre de nombres premiers pour un même intervalle (par exemple de 1000) diminue :
168 dans [1; 1000];
106 dans [10 000; 11 000];
61 dans [100 000 000; 100 001 000].
Ce nombre tend vers 0 pour un intervalle \([x; x + 1000]\), quand \(x \to +\infty\).
Le plus grand nombre premier jamais trouvé date de 2018, et s'écrit avec plus 24 millions de chiffres. Il est égal à \(2^{82 589 933} - 1 = 1\,488\,944\,457...217\,902\,591\).
Un nombre de Mersenne, noté \(M_n\) est un nombre pouvant s'écrire sous la forme \(2^n-1 \;(n \in \mathbb N) \). Un nombre premier de Mersenne est un nombre de Mersenne qui est également premier : c'est le cas du plus grand nombre premier (donné juste au-dessus). On sait que si \(n\) est premier, alors \(M_n\) a une chance d'être premier. De plus, on peut assez facilement savoir si ce type de nombre est premier ou pas (l'algorithme est efficace). De ce fait, les très grands nombres premiers sont cherchés parmi les nombres de Mersenne. Si l'on trace le graphique du nombre de chiffres du plus grand nombre premier connue en fonction de l'année où il a été découvert, on obtient une courbe d'allure exponentielle, et ce grâce à la puissance des ordinateurs toujours croissante.
Les nombres de Fermat, notés \(F_n\), ressemblent aux nombres de Mersenne, mais s'écrivent sous la forme \(2^{2^n} + 1 \;(n \in \mathbb N)\). Ces nombres deviennent vite très grand : \(F_4=65\,537\). Fermat conjecture que \(\forall n,\; F_n\) est premier. Cependant, les calculateurs d'aujourd'hui ont trouvé de nombreux contre-exemples : \(F_5\) est multiple de 641 ... Depuis, on suppose justement que ces nombres ne sont pas premiers.
Il existe de nombreux types de nombres premiers autres que ceux de Mersenne et de Fermat : par exemples les nombres premiers de Fibonacci, de Sophie Germain, de Pythagore, d'Euclide, les nombres premiers jumeaux, cousins, factoriels, primoriels, brésiliens, chanceux, équilibrés, sûrs, semi-premiers, presque premiers, reimerp...