Nombres de Carmichael dans un intervalle donné

On recherche ici les nombres de Carmichael dans un intervalle [n1,n2] donné de N. On reprend le même programme décrit à la page Nombres de Carmichael en le glissant dans une boucle dont les bornes n1 et n2 sont choisies par l'utilisateur.

! Le programme est efficace mais attention cependant au temps de calcul pour des grands intervalles et/ou de grandes valeurs de n au-delà de 10000). Une alerte aura lieu tous les 1000 essais pour éviter de planter votre ordinateur ! Google Chrome et Mozilla présentent l'avantage de mieux s'inquiéter qu'Internet Explorer en cas de non réponse d'un script...

<SCRIPT LANGUAGE=JavaScript>
var n,t
function carmi2()
{
t=0;ok=0;n1="";n2=""
n1=prompt("Intervalle [a,b], donnez a :",n1)
n1=eval(n1);if(n1%2==0){n1++}
n2=prompt("Intervalle [a,b], donnez b :",n2)
n2=eval(n2)
if(!confirm("Intervalle ["+n1+" , "+n2+"]."+"\n"+"Je continue ?"))return
dep=0; //---------- compteur
for (n=n1;n<=n2;n=n+2)   // ------début boucle n varie de n1 à n2 de n1 à n2
{
t=prem(n);flag=1
if (t==1){continue}    // -----n est premier, on boucle sur n
for (a=2;a<n;a++)
{
if (pgcd(n,a)==1)
{
r1=a%n;rn=r1
for (i=2;i<=n;i++) {rn=(rn*r1)%n}
if (rn%n!=r1) {flag=0;break}      // ------on n'a pas a^n congru à a, on sort et on boucle sur n
}
}
if(flag==1)
{
ok=1; //-----pour se souvenir qu'on a trouvé au moins un nb de carmichael
if(!confirm(n+" est un nombre de Carmichael. Je continue ?")) return
dep=n;
}
if(n-dep>1000){dep=n;if(!confirm("Toujours rien ! Je continue ?"))return}
} // ------ fin boucle n1 à n2
if(ok==0){alert("Aucun nombre de Carmichael dans cet intervalle")} else {alert("Fin de recherche.")}
}
// --------------------------------------------------------------------------------------
function pgcd()
{
aa=a
bb=n
while (bb > 0)
{
r = aa % bb
aa = bb
bb = r
}
return aa
}
// --------------------------------------------------------------------------------------
function prem(n)
{
d=0;k=1;t=1
if(n==3||n==5||n==7){return 1}
if(n%3==0) {t=0}
while (d*d<=n && t==1)
{
d1=6*k-1;d2=6*k+1     // ----- un nb premier est de la forme 6k±1
if(n%d1==0 || n%d2==0) {t=0}
k++
d=d2
}
return t
}
</SCRIPT>