Tout nombre non nul possède évidemment deux diviseurs : 1 et lui-même. Il advient que dans le cas de l'unité ces deux diviseurs évidents se confondent.
Or certains nombres ne possèdent pas d'autres diviseurs que ces deux diviseurs 'triviaux', on les appelle les nombres 'premiers' , c'est par exemple le cas de 2, 3, 5, etc...
Les raisons pour lesquelles on refuse à 1 la qualité de nombre premier ne tiennent pas au fait que c'est le neutre de la multiplication mais plutôt au fait que c'est le seul élément inversible de ℕ. Il résulte de la théorie des anneaux que les éléments inversibles n'ont pas à être pris en compte pour les problèmes de décomposition (factorisation), faute de quoi on ne peut énoncer correctement les théorèmes.
On retiendra donc simplement pour le moment que 1 n'est pas premier et qu'on peut prendre pour définition des nombres naturels premiers:
Un nombre est dit 'premier' s'il possède exactement 2 diviseurs.
Sachant que cette définition provisoire ne se généralise pas à d'autres anneaux (même pas au cas des entiers relatifs...)
Vous pouvez générer quelques exemples avec le formulaire ci-dessous:
Donner un entier 0< n ≤ 100000

Message d'erreur éventuel:

La suite des nombres premiers commence donc ainsi:
P={2,3,5,7,11,13,.......}
Le premier problème est de savoir si elle se termine. !!!
On sait depuis l'Antiquité que non.
Cette suite est infinie.
Un raisonnement par l'absurde suffit à le prouver:
Supposons que la suite soit finie, on aurait
P={2,3,5,7,11,13,......,p} où p serait 'le plus grand nombre premier'.
Considérons alors
q=2 × 3 × 5 × ... × p +1
Ce nombre est bien évidemment strictement plus grand que p, et il ne peut avoir aucun diviseur premier, donc aucun diviseur tout court. q serait donc premier ce qui contredit que p est le plus grand des nombres premiers.

Crible d'Eratosthène

Le crible d'Eratosthène est un algorithme rapide pour déterminer les nombres premiers entre 1 et N.
On commence à rayer tous les multiples de 2, puis les multiples de 3, et on continue ainsi.
Prendre le premier nombre non rayé, rayer tous ses multiples stricts.
On s'arrête quand on a dépassé √(N).

Cliquez pour voir le crible
Suivant:

Café Python

Un premier programme naïf pour déterminer les nombres premiers:

Ce programme détermine les nombres premiers, avec une fonction de test.

Ce programme détermine les nombres premiers avec le crible d'Eratosthène.

Ce programme genère la suite infinie des nombres premiers, chacun étant construit à partir de ceux qui le précèdent.

Voici maintenant un exemple d'évaluation paresseuse.

Le coin du C

Pour aller très vite rien ne vaut le langage C. Voici une implémentation du crible d'Eratosthène qui pour s'éxécuter met 60 ms.
On fait ensuite la somme de tous les entiers premiers jusqu'à 2000000, cette sommation prend 5 ms.
Le tout sur un PC portable avec microsoft Vista et 2GB de mémoire.