Forum de mathématiques - Bibm@th.net

<il se peut que l'on ne puisse pas faire grand chose car :
on est obligé de passer par:

pour mettre les index de j dans leur famille respective, qui est donné par Dico={...}
or le fait de refaire la division pour calculer l'index, ne changera rien...

Je pense que la seule possibilité serait de traiter le début d'index dans fam=Dico[j%30] en récupérant le quotient q...
ce qui permet de traiter au fur et à mesure et de ne pas stoker les Pfam....on ne fait qu'une division....

voili voila
@+

{ la nuit permet de classer les idées , pour trier et donner la solution au petit matin....LoLLLL} 

Ca, j'ignorai que le programme, calculer tous les pfam et qu'il les stockait, pour ensuite les traiter un par un..

Effectivement il faut les traiter au fur et à mesure...un par un...dans la limite de n; afin de "modifier" de cribler la liste nombres...

C'est aussi pour cela que l'on pouvait faire pareil pour les j les traiter au fur et à mesure, passez à j suivant , dans la limite de n , puis P_i suivant , au fur et à mesure la liste nombres est modifiée ie; criblée les [1] remplacé par [0].

c'est cette partie centrale du programme qu'il faut voir , "pourtant les temps mis pour initialiser et famille de P_i sont vraiment minime.."
Tu as réduit le temps par plus de 30...

Lorsque je crible avec crible_mod30 que tu avais déjà modifié et avec criblG9y_mod30 qui est le dernier, on divise le temps par 5, pour n = 3 000 000 000 , pour une famille criblée ; de plus je suis limité à 15 000 000 000 environ

pour info: je met les 3 temps, on crible la famille 7[30], pour obtenir les premiers congrus à 23[30]

====== RESTART: E:\Documents\conjecture de Goldbach\crible_modulo30.py ======
Donnez la valeur de N = 30k : 9000000000
Crible mod30 : Initialisation: 13.556423664093018 seconds ---
Crible mod30 : Famille de chaque Pi: 1.1388018131256104 seconds ---
Crible mod30 : Criblage des 8 familles: 70.7617244720459 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 93.17896389961243 seconds ---
On a 48272778 nombres premiers
>>>

==== RESTART: E:\Documents\conjecture de Goldbach\cribleG1_par Famille.py ====
Donnez la valeur de n = 30k : 9000000000
CribleG1_mod30 : Initialisation: 13.322423696517944 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 1.0920016765594482 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 64.2877128124237 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 22.588839769363403 seconds ---
On a 48272778 nombres premiers
>>>

===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py =====
Donnez la valeur de n = 30k : 9000000000
Phase d'initialisation: 0.904801607131958 seconds ---
Famille de chaque Pi: : 1.123201847076416 secondes ---
Criblage des 8 familles: 41.60527324676514 seconds ---
Extraction des premiers n à 2*n : 2.2776038646698 seconds ---

**  48272778 nombres trouvés en 45.91088056564331 secondes **
>>>

tu avais utilisé: fam =Dico[j%30] pour faire appel à une bibliothèque et  pour placer les j dans pfam en fonction du reste de j%30 = Dico={1:0, 7:1, ....etc.., 29:7}
c'est vrai que là , si j = 161, par exemple  avec P_i = 11, pour n=240

il te faut bien avoir Dico[j%30] = 11 et début index = 5; donc Dico={11:2} afin de placer le début_index = 5 dans nombres colonne 2; afin de cribler, ie: marquer les [0] par pas de 11, de 5 à 7 ; dans nombres : c'est à dire, la colonne 2...

Il te fallait bien une fonction qui définisse la colonne où le programme, va placer l'index de j...non ? la colonne 2, correspond à p8 = 11

Pour moi je pensais que Dico={1:0,.......,29:7} te servais dans le programme à fixer la colonne ou Famille de p8, dans nombres...pour ensuite placer l'index de j...

je te met le dernier code, (fais attention, j'ai rajouté ' pour les [i'] afin de l'éditer) :

comment tu fais pour garder les couleurs dans le code...?

celui ci de programme, pour une famille criblée, je suis allé jusqu'à 26 160 000 000 :
>>>
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG9Y_modulo30.py ========== 1[30].….>29[30]
Donnez la valeur de n = 30k : 26160000000
Phase d'initialisation: 2.4804043769836426 seconds ---
Famille de chaque Pi: : 3.135605573654175 secondes ---
Criblage des 8 familles: 131.55503129959106 seconds ---
Extraction des premiers n à 2*n : 6.583211660385132 seconds ---

**  134 171 843 nombres premiers trouvés en 143.754252910614 secondes ** dans p8 = 29

je n'ai fais qu'apporter tes modifications depuis cribleG1....au fur et à mesure de tes instructions et modif... Rien que le bloc s4, il a divisé le temps par 20 au minimum...

ça va être difficile de faire beaucoup plus vite , par contre on risque d'y gagner en mémoire et de pousser la limite n, vers 40 mds...

et autre chose , Dico={1:0........,29:7} me permet de définir la famille que je veux cribler , en modifiant l'ordre ; ainsi que in range (8):
Il se peut que ce soit Pfam,P8=[],[1, 7, 11, 13, 17, 19, 23, 29], qui ne serve plus à rien...dans ta nouvelle version...sauf si c'est lié à
Dico = {1:0.........29:7}

@+

ok ......j'ai compris pour 11//10//3

            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]
                indice=j//10//3  ### C'est lui qui est en cause { mettre indice=[j]//10//3 }
                Nombres_j=nombres[j]
                for index in range(debut_index, nbcell,pi):  et,  for index in range(indice, nbcell,pi):
                    Nombres_j[index] = 0

Mais j , ce ne peut être un index car j = 11, correspond pour n=240 à : 4 +7 où 4 est le reste de 480%7...
,
l'index de j = 11 est : 11/10//3 = 0 est comme j=11 ; ce qui vaut dans Dico[ 1:0, 7:1, 11:2 ....] dans nombres cet index 0, va se positionner sur la première ligne, 3ème colonne; afin de remplacer [1] par [0]
[1, 1, 0, 1, 1, 1, 1, 1],

et P_i = 7, va marquer d'un [0] de 0 à 7..

peut être que le fait de nommer indice = j//10//3 est en contradiction avec la ligne :  for index in range(debut_index, nbcell,pi):

où début_index devrait être nommé indice.....???

Ou encore: Comme dans mon dernier programme j'ai :

il faut peut être écrire :

debut_index=[j]//10//3  # on enlève Pf
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):

voila .....

re

ben oui...
car si je comprend bien supposons dans ton exemple le premier j = 11
l'indice c'est 11//30 = 0

or :  si tu fais 11//10 = 1 et encore 1//3 = 0
donc l'indice qui reste c'est quoi....? 1 ou 0

On devrait avoir dans nombres :

nombres =
[
[1, 1, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1, 1],
]

yoshi]Bonsoir, Re

Tout à fait, car cela fait, pour 40000 P_i en gros 40000 * 8 j , à calculer la position et l'index de dédut
Et si, au lieu de les stocker, on les utilisait au fur et à mesure de leur création ? OUI

oui

qui correspond au début de la phase de Criblage par pas de P_i..

Exact, c'est pour cela que je t'ai dit on ne gagnera peut être que 1 à 2 secondes pour 30 mds et pour une Famille criblée, estimation faite , d'après le temps mis dans la phase Si : Famille de P_i...Donc...???

Position qui est donnée après : if j%3!=0 and j%5!=0: ..; Par la ligne : fam =Dico[j%30]  ...qui par conséquent permet aussi de récupérer le début d'index en utilisant le quotient....Donc de positionner le départ de P_i dans P8, pour le criblage, au lieu de positionner J pour ensuite aller calculer le début d'index dans s3...et criblage dans P8.. 
               

Parfaitement, enchainer sur S3 qui est le criblage dans P8, pour marquer les [0] , dans nombres....par pas de P_i ...

Tu as parfaitement déroulé le fonctionnement du criblage dans le programme...

Le programme est très bien fait comme il est, il n'y aura rien à changer....

Ce serait bien le diable s'il n'y avait rien à voir... Ce ne serra que de la logique et du peaufinage, dans le déroulement des 2 phases S2 et S3..., Mais on ne pourra pas gagner grand chose en principe...Sauf : comme tu as tellement amélioré le fonctionnement du crible depuis l'origine en divisant le temps par 10  voir plus...

Alors pense d'abord à ta revues....Et avec un Grand merci...

Peut être que ce crible te permettra de formaliser mieux que je le fais et d'être le premier à montrer : que le nombre de nombres premiers lorsque n tend vers + l'infinie vaut:
n sur le log "nipeurien" de 2n au minimum ! ...De démontrer que ce ne sont que des corollaires du TNP et Du TFA, d'où en découle la conjecture de Goldbach....et le postulat de Bertrand passera à la postérité...car il ne sert vraiment à rien , concernant la répartition des nombres premiers, surtout de n à 2n.....

@+

re bonsoir

Ce sont les 8 premiers termes de P8, en progression arithmétique de raison 30 et à part 1, qui n'est pas premier, ils vont servir de base pour calculer les [tex]j \in P8[/tex] dans la limite:[0 ; P_i*29] soit au maximum, 15 j pour chaque P_i, afin de cribler les entiers congrus à 2n%P_i, P premier, d'indice i. Soit P_i marquera 8 congrus sur P_i*8 nombres; en partant de l'index de j
Donc l'index de $J\in P8$ est le point de départ, marqué [0] de P_i qui va cribler par pas de P_i.

Au maximum pour P_i = 7 cela donnera 56 nombres ("pas 64"), qui seront criblés par les 5 P_i de bases,[tex]\leqslant\sqrt{2n}[/tex]
car 7*30 = 210 et 210/3,75 = 56. 3,75 et le coefficient pour obtenir les entiers de P8, par rapport aux entiers naturels positif >0 , quelque soit n.

Ce qui donnera pour n= 210 , ou 240 au maximum 39 nombres sur 56 , soit , comme Eratosthène, le crible de Goldbach donnera, 39 premiers sur 56 de n à 2n,Au minimum...

d'où attention à la modification de :

1) l'instruction dans, famille de P_i cette ligne ci-dessous, est la bonne ligne de code :

  ; qui  ne doit pas être modifier avec l'instruction : ,min(pi*29,n) :

Car elle modifie les J de pfam , dans de grandes proportions pour n > 3000, et fausse totalement le crible, en supprimant des j, ce qui a pour effet de supprimer des entiers congrus à 2n%pi , d'où augmentation importante du nombre de nombres premiers de n à 2n , sans même améliorer le temps ce qui est logique , par contre tu auras beaucoup plus de cellules [1] à compter.

C'est pour cette raison, juste dans le poste au dessus, que je t'ai dit tu as raison il ne faut pas toucher à pfam, sauf si on ne l'utilise plus, ["car le problème des j > n n'est que pour les valeur de n < 3000, d'où comme tu le signales, c'est effectivement en aval que tu peux éventuellement améliorer..."].
Il y a une explication très simple, la racine carrée de 2n progresse moins vite que n..! Donc les j, ne pourront plus dépasser n >3000
En exemple :
[tex]\sqrt{600}[/tex] = 24 dans le pire des cas tu as 23*30= 690 très au dessus de n = 300

[tex]\sqrt{3000}[/tex] = 54 dans le pire des cas tu as 53*30= 1590 A peine au dessus de n = 1500

[tex]\sqrt{30000}[/tex] = 173 dans le pire des cas tu as 173*30= 5190 bien en dessus de n = 15000 et en plus aucune erreur possible car la limite F, prime sur la limite n, pour les j; comme tu l'avais remarqué , tu peux très bien avoir un j , le dernier, tel que j_(-1) +2*Pi = 14987 pourquoi pas, donc à la limite de 15000 .

L'instruction : que tu as mise; ,min(pi*29,n, elle marque d'office les premiers de la ligne n°0, qu'elle marque [0] peut être à cause
de ,min, ce qui te donne dans ton premier tableau les fameux cinq 0...mais ensuite, elle fait le contraire elle supprime des j d'où augmentation de cellules [1] est résultat archi faux ; voici le résultat , avec cette mauvaise instruction , et en dessous les 2 tableaux avec la bonne instruction ci-dessus: le temps est identique, mais cela ne durerait pas car plus de[1] prendra du temps pour les compter...!

De la même Façon que ton idée pour compter la somme des 1, était très bonne car, l'inverse n'est pas possible, avec les [0].
D'autant plus, que ce que tu appelles les doublons, poseraient problème, du fait qu'ils correspondent à la décomposition unique en facteurs premiers d'un entiers positif, de n à 2n pour ce qui nous conserne, d'où le corollaire du TFA, un entier positif > 0, peut être congru de façon unique, à l'ordre près de ses facteurs, ce qui donne  des doublons de j ...!
******************************************************************************************************
Python 3.6.5 (v3.6.5:f59c0932b4, Mar 28 2018, 17:00:18) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 300000000
Phase d'initialisation: 0.28080034255981445 seconds ---
Famille de chaque Pi: : 0.28080058097839355 secondes ---
Criblage des 8 familles: 9.063616037368774 seconds ---
Extraction des premiers n à 2*n : 0.6396012306213379 seconds ---

**  15320277, résultat faux nombres trouvés en 10.26481819152832 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 600000000
Phase d'initialisation: 0.514801025390625 seconds ---
Famille de chaque Pi: : 0.561600923538208 secondes ---
Criblage des 8 familles: 19.234833478927612 seconds ---
Extraction des premiers n à 2*n : 1.2636022567749023 seconds ---

**  29579614  , résultat faux nombres trouvés en 21.574837684631348 secondes **

#############################################################################>>>

========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 300000000
Phase d'initialisation: 0.2964005470275879 seconds ---
Famille de chaque Pi: : 0.2964005470275879 secondes ---
Criblage des 8 familles: 8.985615730285645 seconds ---
Extraction des premiers n à 2*n : 0.6396012306213379 seconds ---

**  15072378 nombres trouvés en 10.218018054962158 secondes **  OK
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 600000000
Phase d'initialisation: 0.514801025390625 seconds ---
Famille de chaque Pi: : 0.5772008895874023 secondes ---
Criblage des 8 familles: 18.798032999038696 seconds ---
Extraction des premiers n à 2*n : 1.248002052307129 seconds ---

**  29130002 nombres trouvés en 21.138036966323853 secondes **  OK

Ne touche surtout pas à Pfam, comme tu le pensais...., car le nombre de j, de R à + (k*P_i) =15, dont 8 appartiennent à P8.

Passe un bonweek end
@ A demain, mais ne te sent pas obligé, car il n'y a plus grand chose à modifier sauf si tu as envie de faire dans la foulée, famille de Pi et criblage avec les suppositions du post au dessus et J = 271 par ex:

Donc fam =Dico[271%30]==1 et le quotient, q==9 ; soit Dico[1%30]=Dico[1:0] ; c'est à dire:

fam , Dico(j%30) donne le reste et le quotient q;  Dico(1%30) donne Dico{1:0} de rang 9; pour P8 [1,] et en récupérant le quotient , on a le début d'index pour Dico{1:0} == 9; on part cribler par pas de P_i = 7; de 9 > à 8 dans ton exemple, ...etc

Ou tout simplement, mettre les débuts d'index dans Pfam de 0 à 7 à la place des j, de 0 à 7 et passer à la phase 3 criblage, ce qui supprime la division : ce passage:
for j in range(8):
            debut_index=(Pf[j]-P8[j])//30.
on passe au criblage:
for index in range(debut_index, nbcell,pi):

..ce qui est aussi...faisable...mais pour 2 secondes au grand max , je pense, pour 30mds et pour une famille...??

attend Yoshy:
j'ai repris l'exemple de tes explications en abrégeant ok.. où tu as cité le processus des 2 lignes:

  .. je vais faire dans fam = Dico[j%30] c'est à dire (271 -13) / 30 != 0 , puis (271 - 1) / 30==0  et quotient = 9 donc j'ai ramené cela à :

je vais faire dans: fam = Dico[j%30] c'est à dire (271 -13), 13%30 != 0 , puis (271 -1)= 1%/ 30 == 0  cette ligne calcul le reste
ensuite  c'est  et quotient = 9 ..c'est tout.

Effectivement...puisque c'est le rôle de cette ligne de programme , pour ensuite envoyer Pfam [.......] dans le boc de criblage ..

Donc c'est Exactement ce qu'il faudrait faire ici :,

mais comme ceci:

Dans la foulée, et des que j dépasse > 240 , pour cet exemple , on passe au suivant..non?

tout d'abord, je ne me permettrait pas de penser quoi que ce soit sur tes capacités.....qui m'ont permis de comprendre le processus du déroulement du programme, de tout ce que tu m'as apporté...! et excuse moi , si je m'exprime mal.

Comment alors empêcher J, dans Pfam de dépasser n..?
la seule solution était à mon sens de s'en passer, et de calculer  les J au fur est à mesure
et effectivement le fonction Dico , permet de faire les deux et pourrait être utilisé pour les index, comme tu viens de le voir...
Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}. famille
Dico={. ...................................................}. index

dès lors, je pense que ce problème de limite même en laissant while <= f ne  éviterait de calculer des j qui sont > n inutilement car, il y en a énormément ce, qui bouffe de la mémoire et du temps ..

tout cela était dans le but de finir, afin d'améliorer la partie crible qui te tenait...Car il ne faut quand même pas oublier comment tu as modifié ce programme pour le rendre parfait...
.........................................................................................................................................................
voici d'ailleurs les nombres premiers q de 240 à 480.., du premier crible de base...avant même que je modifie sa limite j<= f
tu en conviens , d'avoir les nombres premiers, ne sert pas à grand chose  ça ne sert pas à grand chose :
.............................................................................................................................................................
===== RESTART: E:\Documents\conjecture de Goldbach\cribleG3_modulo30.py =====
Donnez la valeur de n = 30k : 240
CribleG3 mod30 : Famille de chaque Pi: 0.0 seconds ---
CribleG3 mod30 : Criblage des 8 familles: 0.0 seconds ---
[269, 359, 389, 419, 449, 479, 263, 293, 353, 383, 443, 349, 379, 409, 439, 257, 317, 347, 467, 283, 313, 373, 433, 463, 251, 281, 311, 401, 431, 461, 277, 307, 337, 367, 397, 457, 241, 271, 331, 421]
On a 40 nombres premiers

pour rappel : le programme d'origine :

Là , c'est toi le mieux placé pour juger....! Mais effectivement tu as entièrement raison
@+

re Yoshi

voyons , ils sont fabriqué à partir du reste R de 2n%pi puis on les augmente de k*Pi comme pour fabriquer les multiples de Pi dans Eratosthène ...Pour n=240, et Pi =7 , 480 % 7 == 4, qui est le premier R congru à 480 [7] ,d'où, R  +7+7+7..etc <= n , j'ai tous les entiers
congru à 480[7; de même pour les multiples de 7, en partant de 7.+7+7..<=n]

pour le premier = R +7 ==11, 11 est congru à 480[7]  d'où 480 -11 , ne peut être premier car divisible par 7; propriété des entiers A congru à B [pi] , pi divise la différence A -B,
je te l'ai expliqué..tu n'as peut être pas fait attention..avec tous ces massage.

comme on s'intéresse aux entiers non multiple de 2,3 ou 5, donc à l'ensemble des entiers congrus à 1 modulo 30, ou à Pi modulo 30, pour Pi premier appartenant à [7 : 29] donc : P8= [1,7,11,13,17,19,23,29];
mes entiers > n , qui sont tes candidats > n
et comme on sait que si un entier de cet ensemble appartenant à [ 7 ; n] , n'est pas congru à 2n % Pi, et bien il est premier appartenant à [n ; 2n] , soit nos candidats..je t'ai même expliqué pourquoi j'étais sûr d'extraire tous les nombres premiers appartenant à [n ;2n] en te disant, c'est trivial...:
Car il suffit de barrer de n à 2n les multiples de [[tex]P_i\leqslant\sqrt{2n} [/tex]] selon le principe Eratosthène, mais en utilisant les congruences. ie) marquer les entiers [tex] n\equiv {2n} [p_i] [/tex] de n à 2n, selon ce même principe, mais avec les [tex]P_i\leqslant\sqrt{2n} [/tex] ....!; avec n appartenant aux familles arithmétique P8[....], de raison 30.. D'où tes candidats comme les miens de n à 2n font bien partie de l'ensemble P8, en progression arithmétique..!

ensuite c'est pour cela, qu'on limite pour cribler jusqu'à n avec Pi, les J <= min(j+pi*29, n) en partant de j , car on aura les 8 j  , dont un seul par famille de P8. On partira du rang de ce j par pas de Pi , soit 7 pour cet exemple...

donc il nous faut l'index de départ ou le rang dans sa famille, pour marquer les entiers congrus à 2n%Pi par pas de Pi ....> n/30 puisque l'on est en progression arithmétique de raison 30 dans les 8 familles de P8. Comme le principe d'Eratosthène...

d'où on a besoin d'utiliser p8%30 conjointement avec Dico%30 à) pour l'index, b) pour la famille à qui appartient l'index de j. je te l'ai détaillé , en reprenant tes explication..
tu me dis :

Ah bon..et c'est quoi que tu calcules depuis le début.. 2n%pi...? si c'est pas R, ...?
j = Ri... Attention, tantôt tu écris <n tantôt ⩽... Sois plus rigoureux... ok...

On est bien d'accord, mais tu oublies, dans l'exemple que l'on utilise avec n = 240 quand tu incrémentes les j +2*Pi..tu ne dépasses pas  n...? a QUOI BON , PUISQU' ALORS j n'est plus <= à 240  à quoi sert 'il, c'est 2n - (n-1 = j) qui nous intéresse..pour marquer les n <= 2n,  congrus 2n%pi .c'est pour cela que dans pfam il est inutile d'avoir des j >= 240

ton tableau que j'ai bien compris min (29*pi) mais avec n=240 comment limiter avec pi = 11, puis 13, puis 17 et 19 que j lorsqu 'on les teste et qu'on les incr , on s'arrête à n<= 240...

pi> 5   29*pi    n     min(29*pi,n)
             
  7     203     240       
11    319     240    480 -253 n'est pas entre n et 2n..il ne peut surement éliminer un entier non premier de n à 2n   
13    377     240   ..etc ..480 - 353, il est > 240, d'où il ne peut supprimer un multiple de[tex]P_i\leqslant\sqrt{2n} [/tex] de n à 2n
17    493     240   ...etc ..480 -259, il est > 240, d'où il ne peut supprimer un multiple de[tex]P_i\leqslant\sqrt{2n} [/tex] de n à 2n
19    551     240    480 - 499  =..? > 240 et > 480 ....idem....

Le but du crible est bien d'éliminer entre n et 2n, les entiers non premiers,  ie): multiple de[tex]P_i\leqslant\sqrt{2n} [/tex]; en marquant [0]:
les entiers <= n, qui sont congru à 2n%Pi.

avec effectivement: Tu veux parler de modulo pi avec pi∈Pi ? bien sûr , et Pi <= sqrt de 2n...

on a bien dans le processus :
après les 2 testes :if j%3!=0 and d_c!=5:

  j = X, appartenant à [7;n] et il n'est pas multiple de 3, ni de 5

donc cette ligne:
               fam =Dico[j%30] ["calcule à qu'elle famille X appartient si R==0, et comment on obtient en même temps le quotient
                if pfam['i][fam] == 0:  ..........................
                    pfam['i][fam] = j    ..........................
ce qui nous donnerait aussi l'index de X, et on par pour cribler , avec les instructions qui vont avec....on ferait le criblage à la suite..tu as détaillé toi même comment on obtient l'index dans le processus.. index = ((pfam[i'][j] - p8[j])// 30).
comme le fait ce bloc en dessous , sans avoir besoin d'appeler à nouveau pfam[0], puis [1]...[4]

je reprend ton exemple post#194: Exemple avec j=0 : Pf[0] c'est Pfam[1][0] qui vaut 271 (> 240) inutile de calculer...
              ici debut_index= (271- 11)//30 = 9  = quotient  (Le 1 c'est P8|0]

bloc que j'utilise dans la version G8Y par famille, et qui marche aussi bien que la dernière dans G9y peut importe l'une ou l'autre
.................................................................................................

.......................................................................................

si on teste, puis on détermine la fam , et on index, j alors dans la foulée  on peut aller cribler .....!
sans avoir à passer par le bloc ci dessus qui fait le même travail que le bloc famille pour chaque Pi ... qui lui ne fait que remplir pfam[n] pour le bloc on crible les 8 colonne,
alors qu'il place les j dans les bonnes famille ...tu as détaillé ce processus , moi j'ai vu connaissant l'algorithme, que l'on pouvait obtenir le quotient pour indexer j et donc aller cribler..dans la foulée  ...

donc  on aurait pas non plus besoin "en principe"  de faire appel à: pfam.append([0,0,0,0,0,0,0,0]) que l'on supprime, puisqu'il n'est plus question de remplir et de positionner les j, dans pfam pour les envoyer ensuite au bloc criblage......non..?

pour répondre au 2 posts ci -dessus, en espérant t'éviter à nouveau tes explications , suivant ces dernière j'ai répété ton processus,dans l'ordre en partant de R; afin de te montrer ce problème de dépassement de j >= n , et dans ton cas précis n=240
...................................
Tes explications du 7/5, post #194 ;  et 85
Désolé, je me suis absenté...
n=240
nbcell=240//30=8 (de 0 à 7)
Primes_init=[7, 11, 13, 17, 19]  récupérés grâce à l'appel à la def eratostene.
Pfam : (en gras les j > n=240 , il y en a 1/3
[
[151, 67, 11, 193, 137, 109, 53, 179],                --->Pf =   Pfam[0]  ;  pi=Primes_init[0] = 7
[271, 7, 161, 73, 227, 139, 932, 29],                  --->Pf =   Pfam[1]  ; pi=Primes_init[1]  =11
[181, 337, 311, 103, 77, 259, 233, 389],            --->Pf =   Pfam[2]  ; pi=Primes_init[0] = 13
[361, 157, 191, 463, 497, 259, 293, 89],             --->Pf =   Pfam[3]  ; pi=Primes_init[0] = 17
[271, 157, 461, 43, 347, 499, 233, 119]              --->Pf =   Pfam[4]  ; pi=Primes_init[0] =19
Suite…
***********************************************************************************
n=240,
Pi = [7,11,13,17,19] index de 0 à 4, et pfam de 0 à 4
j doit être au maximum <= f = pi*29 et et si j >= n break , on passe à Pi et R suivant;  tel que j <= n {ce que je n'ai pas réussi à faire ce matin car il y a une limites maxi pour les Pi petits  donc j <= f et si j >= n break , pour les Pi plus grands, tel que Pi*29 > n limite donc j >n l'instruction break , fait passer à Pi et R suivant; car ils cribleront  moins de 8 fam...

On peut peut-être procéder comme ci-dessous :

Exemple, suivant le processus de tes deux exemples entre phase s2 et phase s3: pour ne faire qu’un processus

On a déjà fait Pi[0] =7 , pfam[0]
………..
d’où en exemple, on passe à Pi[1] suivant = 11 ;  f = 11*29 = 319 > n… ? alors  on doit limiter dans pfam[1] la limite de j :

[«  ceci est ton ex pfam[1]: [271, 7, 161, 73, 227, 139, 293, 29],                  --->Pf =   Pfam[1]  ; pi=Primes_init[1]  =11
suivant le processus ci-dessous : »]

pi[1] =11, R(1) = 7

j=7
à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[7%30]= Dico[7]est le quotient ==(0)
soit fam 1 et puisque Pf[21], (c'est à dire Pfam[0][1]) index(0)) on part cribler par pas de Pi[0] = 11 de (0) à 8 (nbcell = 8)et on passe à j suivant.

J =7+22= 29
à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[29%30]= Dico[29]est le quotient ==(0)
soit fam 6 et puisque Pf[6], (c'est à dire Pfam[0][6]) index(0))on part cribler par pas de 11 de (0) à 8 (nbcell = 8)et on passe à j suivant.
J= 29+22 =51

à t’on j%3==0 ou j%5 ==0
oui : On passe directement au j suivant :: j = 51+22 = 73

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[73%30]= Dico[13]est le quotient ==(2)
soit fam  et puisque Pf[3], (c'est à dire Pfam[0][3]) index(2))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.
J =73+22 = 95

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 95+22 = 117

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 117+22 = 139

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[139%30]= Dico[19]est le quotient ==(4)
soit fam  et puisque Pf[5], (c'est à dire Pfam[0][5]) index(4))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.
J = 139 +22 = 161

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[161%30]= Dico[11]est le quotient ==(5)
soit fam  et puisque Pf[2], (c'est à dire Pfam[0][2]) index(5))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.
J = 161 + 22 =183.

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 183+22 = 205

à t’on j%3==0 ou j%5 ==0
oui ; On passe directement au j suivant :: j = 205+22 = 227

à t’on j%3==0 ou j%5 ==0
non
donc fam =Dico[j%30]=Dico[227%30]= Dico[17]est le quotient ==(7)
soit fam  et puisque Pf[4], (c'est à dire Pfam[0][4]) index(7))on part cribler par pas de 11 de (0) à 8 (nbcell = 8) et on passe à j suivant.

J = 227 +22 = 249 > n = 240 Break  Cela met fin au processus de pfam[1]; on passe Pi[2] et R[2] .... ;
le criblage des fam, serra dans l'ordre de [p8 = [1,6,3,5,2,4] ] sur 8......> pi suivant.

on passe à Pi [2] suivant et R[2] ; on réitère le processus. Jusqu’au dernier Pi[4] .

Les Pi étant de plus en plus grand, le processus serra de plus en plus court, de ce fait l’algorithme accélère … en phase de criblage final.

Mais cela nous évite de passer par cette étape :

for i in range(lenpfam) :
        for j in range(8):
            index = int((pfam['i][j] - p8[j]) / 30)           
            while index < nbcell:
                nombres[j][index] = 0
                index += p['i]
………………………………………….

je te joins ci dessous, les entiers > 240 qui sont premiers , pour tes testes . des 8 fam P8[7.11.13.17.19.23.29.31]
..............................................................]
0     0      223    227    229    233    239    241
0     251     0      257     0     263    269    271
277  281   283       0      0      293      0       0
307 311  313     317      0       0       0      331
337     0       0    347    349    353    359     0
367     0    373     0    379    383     389     0
397    401     0     0    409      0     419    421
0     431    433     0     439    443    449     0
457  461   463   467      0      0      479      0
..............................................................]
@+ bonne soirée

voila avec un petite crible : pour N =150 ....qui va éclaircir

B_)                                   
crible_mod30 :  N = 150; Pi ≤ sqrt 2N ; Pi = 7,11,13,17. R = 6,3,1,11                                   
N = 30k , on part du reste R º p8[30] une fois défini les 8 Ri de départ.       

On détermine les Ri = j appartenant à p8, pour chaque Pi et on crible; ensuite on réitère avec le Pi suivant:...>limite 150/30 = 5
                                                   
6 + 7   = 13 ; +14 ; 27 +14 = 41 + 14; 55+14 ; 69 +14 = 83 +14 = 97 +14 ; 111; +14 ;125 ;+14 =139 +14  >150 fin.                                                       
3 + 2*11 =25; +22 = 47 ; +22 ;69 + 22= 91 + 22 = 113 +22 ; 135 +22 . > à  150Fin                                                       
1 + 2*13 = 27 +26 = 53 +26 = 79 +26; 105 +26 = 131 ; +26 > 150.fin                                                       
11 + 2*17 = 45; +34 = 79; +34 = 113 ; +34 =147 +22...>150fin                                                       
                           
                                   
    A cribler    : serront marqués [0] les nombres en gras
                           
1    7    11    13    17    19    23    29       
31    37    41    43    47    49    53    59       
61    67    71    73    77    79    83    89       
91    97    101    103    107    109    113    119       
121    127    131    133    137    139    143    149   

    candidat à la primature

151    157    161    163    167    169    173    179       
181    187   191    193    197    199    203    209       
211    217    221    223    227    229    233    239       
241    247    251    253    257    259    263    269       
271    277    281    283    287    289    293    299       

donc ne sont pas premiers les candidats en gras