Crible d'Eratosthène

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Crible d'Ératosthène @ Liste de nombres premiers dans un intervalle [n1,n2]

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 :

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.

Programmation de l'algorithme en JavaScript :

Nous allons rechercher à l'aide de l'ordinateur tous les nombres premiers inférieurs à 1000. On crée la liste des entiers de l'intervalle [2,1000] : a(2) = 2, a(3) = 3, ... , a(1000) = 1000. Initialement, le tableau a[ ] contient les entiers de 2 à 1000. On balaye ensuite le tableau si un a[k] est non nul, on efface (mise à zéro) ses multiples à partir du rang suivant et jusqu'à 1000 :

<SCRIPT LANGUAGE=JavaScript>
function go()
{var a=new Array()
for(k=2;k<=1000;k++) {a[k]=k}
for (k=2;k<=1000;k++) // effacement si a[m] multiple de k
{if (a[k]!=0)
{for(m=k+1;m<=1000;m++)
{if (a[m]!=0 && a[m]%k==0) {a[m]=0}
}}}
co=0;
wdow=open("","crible","height=500,width=500","scrollbars=1");
wdow.document.write("<PRE>");
for (k=2;k<=1000;k++)
{co++;
if (co%35==0) {wdow.document.writeln("")}
if (a[k]>0) {wdow.document.write(a[k]+" - ")}
}
}
</SCRIPT>

Une très belle étude du crible sur Interstices (INRIA/CNRS) : » Étude des nombres premiers : »