Nombres premiers: Crible avec cycle additif Bis
Description
Voici la première suite de l'article Crible avec cycle additif.
où on utilise explicitement les cycles additifs {2}, {2,4}, {4,2,4,2,4,6,2,6},
{2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10},
basés respectivement sur les nombres premiers déjà connus [2], [2,3], [2,3,5], [2,3,5,7], pour "éliminer" (dans un crible d'Eratosthène) de façon anticipée les candidats multiples de ces nombres premiers.
Si d'autres méthodes sur les nombres premiers vous intéressent:
==> Résumé de mes articles sur les nombres premiers.
Avec CycleOut (ou avec CycleOut.html du zip), vous pouvez obtenir (par exemple) les 664579 nombres premiers <= 10000000 en une ou deux secondes (calcul et affichage) !
Les fonctions Cycle235 et Cycle2357 ne diffèrent que par l'initialisation des variables pri, len, gap et cyc, qui définissent le cycle utilisé.
Précisons ces valeurs et montrons comment elles évoluent:
pri est le nombre premier à partir duquel on applique le cycle additif pour trouver les candidats suivants.
gap désigne la somme des éléments du cycle, et qui correspond au produit des nombres premiers < pri: 2=2, 6=2*3, 30=2*3*5, 210=2*3*5*7, ...
len est le nombre l'éléments du cycle qui est obtenu en multipliant les nombres premiers diminués de 1: 1=(2-1), 2=(2-1)*(3-1), 8=(2-1)*(3-1)*(5-1), 48=(2-1)*(3-1)*(5-1)*(7-1), ...
gap/len est le facteur de réduction de la mémoire utilisée pour le crible.
Une manière de calculer un "cycle" particulier serait d'utiliser un crible pour les entiers entre (pri+1) et (pri+gap), d'y annuler les multiples des nombres premiers plus petit que pri, puis de relever la différences des indexes consécutifs des éléments restants.
Mais nous allons construire l'objet Cycle muni d'une fonction Next() qui, à partir d'un cycle donné, permet de calculer "récursivement" le cycle "suivant".
Créons l'objet Cycle et la fonction Next():
Le programme Cycles.html,qui donne les résultats suivant, vous permet de tester cet objet:
L'élément max n'est calculé que pour le dernier cycle.
Voici un autre algorithme assez semblable: algorithme additif et itératif.
Nous voici prêt pour réaliser un code "général", basé sur Cycle235 et Cycle2357, qui permet l'utilisation d'un cycle de niveau quelconque.
Limitons-nous tout de même au moins au domaine des entiers 32 bits: gap < 2³², donc 2 <= pri <= 29.
La capture jaune de l'article montre les résultats du code Cycle_Test.html.
Quelle déception !!!
Les résultats ne s'améliorent que jusqu'à pri=11, puis, ils s'empirent très rapidement.
En ce qui concerne le temps de calcul, il semble donc illusoire d'aller plus loin que le cycle basé sur [2,3,5,7]: pri=11, len=48, gap=210; gap/len=4.375; cyc=
[2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10].
Ou serait-il possible d'améliorer le passage de Cycle23 à Cycle235, Cycle2357 ou Cycle.Sieve ?
Le gain en place mémoire gap/len pour le crible sv s'améliore de moins en moins, surtout qu'il faut ajouter la taille du cycle lui-même, qui augmente rapidement.
Pour la troisième suite de cet article, je vais essayer de tenir compte de ces remarques.
où on utilise explicitement les cycles additifs {2}, {2,4}, {4,2,4,2,4,6,2,6},
{2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10},
basés respectivement sur les nombres premiers déjà connus [2], [2,3], [2,3,5], [2,3,5,7], pour "éliminer" (dans un crible d'Eratosthène) de façon anticipée les candidats multiples de ces nombres premiers.
Si d'autres méthodes sur les nombres premiers vous intéressent:
==> Résumé de mes articles sur les nombres premiers.
Avec CycleOut (ou avec CycleOut.html du zip), vous pouvez obtenir (par exemple) les 664579 nombres premiers <= 10000000 en une ou deux secondes (calcul et affichage) !
Nombres premiers: Crible avec cycle additif Bis
Les fonctions Cycle235 et Cycle2357 ne diffèrent que par l'initialisation des variables pri, len, gap et cyc, qui définissent le cycle utilisé.
Précisons ces valeurs et montrons comment elles évoluent:
prms connus pri len gap gap/len cyc candidats restants
- 2 1 1 1 {1} 2,3,4,5,6,7,8,...
2 3 1 2 2 {2} 3,5,7,9,11,13,15,17,...
2,3 5 2 6 3 {2,4} 5,7,11,13,17,19,23,25,29,...
2,3,5 7 8 30 3.75 {4,2,4,2,4,6,2,6} 7,11,13,17,19,23,29,31,37,41,...
2,3,5,7 11 48 210 4.375 {2,4,2,4,6,2,6,4,2,4,6,...} 11,13,17,19,23,29,31,37,41,43,47,...
2,3,5,7,11 13 480 2310 4.8125 {4,2,4,6,2,6,4,2,4,6,6,...} 13,17,19,23,29,31,37,41,43,47,53,...
2,3,5,7,11,13 17 5760 30030 5.21354 {2,4,6,2,6,4,2,4,6,6,2,...} 17,19,23,29,31,37,41,43,47,53,...
2,3,5,7,11,13,17 19 92160 510510 5.53939 {4,6,2,6,4,2,4,6,6,2,6,...} 19,23,29,31,37,41,43,47,53,...
...
pri est le nombre premier à partir duquel on applique le cycle additif pour trouver les candidats suivants.
gap désigne la somme des éléments du cycle, et qui correspond au produit des nombres premiers < pri: 2=2, 6=2*3, 30=2*3*5, 210=2*3*5*7, ...
len est le nombre l'éléments du cycle qui est obtenu en multipliant les nombres premiers diminués de 1: 1=(2-1), 2=(2-1)*(3-1), 8=(2-1)*(3-1)*(5-1), 48=(2-1)*(3-1)*(5-1)*(7-1), ...
gap/len est le facteur de réduction de la mémoire utilisée pour le crible.
Une manière de calculer un "cycle" particulier serait d'utiliser un crible pour les entiers entre (pri+1) et (pri+gap), d'y annuler les multiples des nombres premiers plus petit que pri, puis de relever la différences des indexes consécutifs des éléments restants.
Mais nous allons construire l'objet Cycle muni d'une fonction Next() qui, à partir d'un cycle donné, permet de calculer "récursivement" le cycle "suivant".
L'objet Cycle
Créons l'objet Cycle et la fonction Next():
function Cycle() {this.pri=2; this.len=1; this.gap=1; this.cyc=[1];}
Cycle.prototype.Next=function() {
var cyc=[],e=this.cyc[0],r=e,i=0,j=0,p=this.pri,len=this.len*(p-1);
do {
if (++i>=this.len) i=0; // plus rapide que d'utiliser [i%this.len]
if ((r+=this.cyc[i])%p) {cyc[j++]=r-e; e=r;}
} while (j<len);
this.pri+=this.cyc[0]; this.len=len; this.gap*=p; this.cyc=cyc;
}
Le programme Cycles.html,qui donne les résultats suivant, vous permet de tester cet objet:
Calcul des cycles: pri=2, len=1, gap=1; gap/len=1; temps de calcul: 0 ms cyc=[1] pri=3, len=1, gap=2; gap/len=2; temps de calcul: 0 ms cyc=[2] pri=5, len=2, gap=6; gap/len=3; temps de calcul: 0 ms cyc=[2,4] pri=7, len=8, gap=30; gap/len=3.75; temps de calcul: 0 ms cyc=[4,2,4,2,4,6,2,6] pri=11, len=48, gap=210; gap/len=4.375; temps de calcul: 0 ms cyc=[2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10] pri=13, len=480, gap=2310; gap/len=4.8125; temps de calcul: 0 ms cyc=[4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,12,10,2,4,2,4,6,2,6,...] pri=17, len=5760, gap=30030; gap/len=5.213541666666667; temps de calcul: 0 ms cyc=[2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,...] pri=19, len=92160, gap=510510; gap/len=5.539388020833333; temps de calcul: 5 ms cyc=[4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,...] pri=23, len=1658880, gap=9699690; gap/len=5.847131799768518; temps de calcul: 91 ms cyc=[6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,6,...] pri=29, len=36495360, gap=223092870; gap/len=6.112910517939815; temps de calcul: 836 ms cyc=[2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,6,4,...] Élément max: 40
L'élément max n'est calculé que pour le dernier cycle.
Voici un autre algorithme assez semblable: algorithme additif et itératif.
Cycle_Test.html
Nous voici prêt pour réaliser un code "général", basé sur Cycle235 et Cycle2357, qui permet l'utilisation d'un cycle de niveau quelconque.
Limitons-nous tout de même au moins au domaine des entiers 32 bits: gap < 2³², donc 2 <= pri <= 29.
Cycle.prototype.Sieve=function(mx) {
var e,h=this.len*Math.floor((mx-this.pri)/this.gap);
var j,p,p2,mm=Math.floor(Math.sqrt(mx)),q,sv=[];
for (j=0,p=this.pri+this.gap*(h/this.len); p<=mx; p+=this.cyc[j++]) h++; // sv=new Array(h)
for (i=0; i<h; i++) sv[i]=true;
for (i=0,p=this.pri; p<=mm; p+=this.cyc[(i++)%this.len])
if (sv[i]) { // if p is prime
var p2=p*2,pl=p*this.len,pp=p*p;
for (k=0,q=this.pri; k<this.len; q+=this.cyc[k],k++)
for (j=pp; j<=mx; j+=p2)
if ((j-q)%this.gap==0) {
for (e=k+this.len*((j-q)/this.gap); e<h; e+=pl) sv[e]=false;
break;
}
}
return sv; // primes < pri not included
}
La capture jaune de l'article montre les résultats du code Cycle_Test.html.
Quelle déception !!!
Conclusion (provisoire)
Les résultats ne s'améliorent que jusqu'à pri=11, puis, ils s'empirent très rapidement.
En ce qui concerne le temps de calcul, il semble donc illusoire d'aller plus loin que le cycle basé sur [2,3,5,7]: pri=11, len=48, gap=210; gap/len=4.375; cyc=
[2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10].
Ou serait-il possible d'améliorer le passage de Cycle23 à Cycle235, Cycle2357 ou Cycle.Sieve ?
Le gain en place mémoire gap/len pour le crible sv s'améliore de moins en moins, surtout qu'il faut ajouter la taille du cycle lui-même, qui augmente rapidement.
Pour la troisième suite de cet article, je vais essayer de tenir compte de ces remarques.
Codes Sources
A voir également
- Nombres premiers: Crible avec cycle additif Bis
- Afficher les n premiers nombres premiers java - Forum Java
- Nombres en árabe ✓ - Forum Delphi / Pascal
- Convertir chiffres romains en nombre arabe ✓ - Forum Delphi / Pascal
- Somme des n premiers entiers - Forum Visual Basic 6
- Écrivez un programme Java (Premiers.java) qui permet d'afficher - Forum Java
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.