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.

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 :


© Serge Mehl - www.chronomath.com