Je pense que ta modification et le changement de position dans le calcule des restes = à 2n%pi à ralenti le programme résultat ci-dessous
avec d_c !=5 et j%3!=0
*$Donnez la valeur de n = 30k : 240000000
CribleG5 mod30 : Initialisation: 2.8548049926757812 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.10920023918151855 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 11.715620517730713 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 4.929608583450317 seconds ---
On a 12194880 nombres premiers
- eratostene retourne directement premiers[3:]. Pourquoi retourner la totalité, la récupérer et ne prendre qu'à partir de 7 ?
parce que eratostène extrait les premiers dont le crible à besoin :
\(\leqslant\sqrt{2n}\) et > 5 car on est dans les 8 familles d'entiers congrus à 1 ou à P[30] avec p premier [7;29] ce qui donne bien les 8 familles c'est à dire les 8 suites arithmétique de raison 30 , de premier terme 1 ou P ci-dessus...
la fonction Criblemod30(n) ne retourne plus la liste premiers : ça ne servait à rien. Je retourne son nombre d'éléments...
tu veux dire les nbcell ==[1], qui sont les nombres premiers q de nà 2n...bien sûr...
dans eratostene effectivement il retourne les premiers > 5 , j'ai laissé car ça ne gênait pas , mais effectivement cela fait une ligne de programme en plus , dans def cribl_mod30
En examinant la liste r (normal, puisque on a écrit j=r['i]), j'ai pu constater quelles contenait des multiples de 2,3 et 5...
ça c'est logique, mais don on a pas besoins puisque les 8 familles on pour reste %9 = [1 ,4,7] pour les 4 familles [1,7,13 19] de raison 30 ; %9 = [2 ,5,8] pour les 4 familles [11,17,23,29] il suffit de faire la somme des chiffres de j pour savoir à quelle famille ils appartiennent
principe de la preuve par 9..
on sait : que 8j sur 15 appartiennent au 8 familles et que les 7 autres j sont d_c==5 et j%3==0 ...
on ne pourra pas les contourner sans passer par un ordre qui élimine le test et fait passer au j suivant...
par exemple pour chaque pi, on a la liste des 15j < f.
si j ==dico%30 on positionne on crible retour aux j suivant elif (j est != dico%30) donc on passe au j suivant...point barre.
criblait les 8 familles pose justement ce problème ...("dans l'algorithme nbpremier.win") on l'a programmé, en c++ , mais par famille il y a 15 ans...
crible mod30 je crible par famille: la famille 7
le début ne change en rien ...
mais dans le criblage et les j on a juste besoin de R =2n%pi, la limite j <= f ne changerait pas mais on le fait au fur et à mesure et cela ne peut dépasser f...puisque
j= 7%30 == 0 serra dans les 15 j , comme le crible ci-dessus...
si R %2==0 += pi ; il est impair et devient j ; ensuite j += incr wile d_c==7 , il n'y a que deux cas possible , ok, donc on positionne j qui donne la position du départ de 7, pour le criblage des nbcell toutes les 7 cellules , puis retour à Pi suivant et R suivant, on réitère.
elif : j += incr wile d_c==7 donc ok par obligation ...et position, crible, retour pi et R suivant; réitération...!
si R != d_c==7 donc j += incr, wile d_c==7 ; j != d_c== 7 , j+=incr wile d_c==7 ; il n'y a que deux cas possible , donc
: j, d_c == 7 ok par obligation .. on le positionne, pour le départ de pi qui va cribler ; retour , pi et R suivant; réitération...!
ça va beaucoup plus vite.....!
le consommateur de temps c'est la position des 8j et le criblage des 8 familles modulo pi..... car marquer d'un [0] par exemple toutes les (pi = 7) cellules , sur un million de cellules par famille.... c'est longuet...; compter les [1] normalement c'est beaucoup plus rapide...