Petite entrée en matière...
Tout d'abord, une petite définition...Ainsi, on décomposer tout entier en facteurs premiers, c'est-à-dire en une multiplication de nombres premiers (le seul facteur premier étant le nombre lui-même s'il est premier).
Exemple: 438 = 2 x 3 x 73 ; 2, 3 et 73 n'ont pas de diviseur entier autre que 1 et eux-mêmes, et sont donc premiers.
Il existe plusieurs algorithmes pour déterminer si un nombre est premier, certains déterministes, d'autres probabilistes (c'est-à-dire qu'il existe une probabilité (très faible) de se tromper lors de la décision de primalité du nombre). Le plus simple de ces algorithmes consiste à tester tous les diviseurs possibles de n, de 2 à racine carrrée de n. Si on n'en trouve aucun, c'est que n est premier. Je ne détaillerai pas ici les autres algorithmes, d'autres pages le font très bien.
On approfondit !
Intéressons-nous maintenant à la répartition de ces nombres premiers parmi les entiers. Regardons par exemple les 20 premiers nombres premiers:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73
Une première remarque est qu'il n'y a pas de nombres pairs (sauf 2), car ils sont tous divisibles par 2; de même, il n'y a aucun multiple de 3, 5, 7, et d'aucun nombre; on repère aisément les multiples de 5 (nombres se terminant par 0 ou 5), et on peut les éliminer tout de suite. Un nombre premier se termine donc par 1, 3, 7 ou 9 (sauf 2 et 5).
Passé ce stade, on ne peut pas dire grand-chose de plus, si ce n'est que la répartition est plutôt chaotique et imprévisible. En fait, il n'existe pas à l'heure actuelle de formule donnant le énième nombre premier (et si une telle formule existe, son découvreur sera très riche). Il existe juste quelques fonctions dont l'ensemble-image contient une très forte proportion de nombre premiers (tout ceci est expliqué sur cette page).
Une autre façon d'essayer de cerner la répartition des nombres premiers est de les placer sur une spirale; c'est le principe de la spirale d'Ulam: on place tous les entiers en spirale, on raye ceux qui sont premiers, et on regarde quel genre de dessin ça donne (ensuite, la conclusion peut changer selon la forme que ça prend).
Sur ce principe, on peut construire une première spirale de 49 éléments, et rayer les nombres premiers, ça donne ça:
On peut ici observer plusieurs alignements, notamment (5, 17, 37) et (47, 23, 7, 19). De plus, une diagonale sur deux est vide de nombre premiers (sauf celle qui comporte 2); la raison est toute simple: une diagonale sur deux est composée uniquement de nombre pairs, donc pas premiers; il est donc relativement logique que les nombres premiers apparaissent par alignements puisqu'ils sont tous sur les diagonales "impaires". A une plus grande échelle, voyons ce que ça donne:
Cette fois, les nombres vont de 1 à 516961 ! (1 pixel = 1 nombre, les nombres premiers sont en blanc)
A priori, à part quelques alignements diagonaux, il n'y a rien de flagrant, même à une "grande" échelle; celà tiendrait plutôt de la flaque de vomi un chouïa filandreuse. On aurait pu espérer une structure fractale, mais ça ne semble pas être le cas, ou alors ce n'est pas visible à cette échelle. Le problème est que si on prend une échelle encore plus grande, il faut un écran encore plus grand pour voir le résultat d'une vue d'ensemble. C'est la première limitation physique de cette expérience :-)
Pour les courageux surdoués...
Voici quelques problèmes qui restent à résoudre à l'heure actuelle (et depuis des siècles)
A voir également...
Allez donc jeter un oeil sur ce site plutôt bien fait!