Salut,
Je na ,,sai,s pas si vraiment tu as compris que dans le CribleG1..ou..6 ,
L'art d'enfoncer les portes ouvertes...
Je t'ai toujours dit que je n'étais intervenu dans ton programme qu'au niveau de la technique et que j'allais devoir me pencher sur le fond.
La seule façon de plonger était d'écrire ma propre version. J'ai annoncé un procédé
naïf...
Naïf, mais logique, quand même.
J'ai chargé l'ensemble des $P_i$ que j'allais utilisr : tous
\(\leqslant \sqrt{2n}\).
Ensuite, étant donné qu'une condition nécessaire pour qu'un nombre nb tel
\(n<nb<2n\) est qu'il soit un multiple de 30, plus 1, 7,11, 13, 17, 19, 23 ou 29, je teste un un par les restes de ces nombres (30k+b) avec chacun des $P_i$, je sors de la boucle dès que l'un des restes est nul et je mets mon drapeau (flag) à 0.
Si aucun reste n'est nul et que j'ai effectué toutes les divisions, alors, j'incrémente le nombre de premiers de 1.
Mon système marche mais est bien trop lent.
J'ai employé le qualificatif de
prohibitif...
Ce qui prouve que le procédé est peut-être logique mais pas optimisé du tout...
C'est là que tu interviens et ce qui m'intéresse est le pourquoi : si je connais la réponse au pourquoi, le comment, j'en fais mon affaire...
Donc allons-y et t'es pas sorti de l'auberge.
on ne fait que 8 divisions par Pi, afin de positionner j = Ri dans une des 8 familles le reste ensuite c'est à dire le criblage c'est du comptage principe Eratosthène mais par Famille, donc obligatoirement modulo Pi*30...!
Ce n'est fondamental pour toi, que parce que tu maîtrises ton algorithme...
Pour moi, c'est une phrase creuse...
1. Appelons un chat un chat
a) Qu'est-ce que Pi ? Ce que moi j'ai noté pi soit p['i] dans ton prog ?
J'ai une habitude : je fais commencer les listes par des majuscules et les nombres par des minuscules (ce n'est pas standard, c'est un choix personnel... Je vais d'ailleurs modifier le nom de ma variable b en ajout en minuscules...
b) Il est recommandé par contre d'utiliser des noms "transparents", alors j=Ri, hein...
Que représente j exactement ? Qu'appelles-tu Ri ? je dois me reporter au dernier "programme commun" ? R=[nn%pi for pi in p] ?
c)
afin de positionner j = Ri dans une des 8 familles. Tes 8 familles regroupent les nombres du type 30k+1, 30k+7, 30k+11... 30k+29
2. Procédé
a) Si effectivement ton R =[nn%pi for pi in p], cela veut dire que
pour n=1500, on a, avec tes notations :
p=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
et
r (ou R ?) =[4, 8, 10, 8, 17, 10, 13, 24, 3, 7, 33, 39, 32]
r est l'ensemble des restes de 3000 dans la division avec chacun des p['i]... Je ne m'étais jamais posé de questions de fond.
Et ce sont ces restes que tu traites l'un après l'autre via la variable j et que tu incrémentes de incr=29*p['i] à chaque tour jusqu'à être supérieurs à la limite f = j+29*p['i]...
Donc pour j=4 : 4 est pair, tu corriges en j=4+7=11 (oui, 3000%7=4) mais pourquoi ? pourquoi pas une autre valeur multiple de 7 ?
Quelle est la "philosophie" qui sous-tend ça ?
Puis tu testes 11 : ni congru à 0 mod 3 ni mod 5... Tu traites..
Puis que tu aies traité ou non, tu passes j de 11 (ou autre) à 11 + incr, Pourquoi augmenter de cette valeur précisément ?
b)
Prenons "au pif" un reste R =1 et son Pi =7.... Pour quelle valeur de n ?
Parce que pour n =1500, aucun des r['i] ne vaut 1...
Ri = J
1, %9 = 1 famille 30k+1
15 %9 =6
29 %9 = 2 famille 30k+29 = 29
Et ce 9, tu le sors d'où ?
1%9 =
1 famille 30k+
1 là je me dis, pourquoi pas ?
Et arrive
29 %9 =
2 famille 30k+
29 = 29 Ah ????....
Et voilà pfam :
[[151, 67, 11, 193, 137, 109, 53, 179], [151, 217, 41, 283, 107, 19, 173, 239], [361, 127, 101, 283, 257, 49, 23, 179], [331, 127, 161, 433, 467, 229, 263, 59], [511, 397, 131, 283, 17, 169, 473, 359], [631, 217, 401, 493, 677, 79, 263, 539], [361, 187, 71, 13, 767, 709, 593, 419], [241, 427, 551, 613, 737, 799, 923, 179], [151, 817, 521, 373, 77, 1039, 743, 299], [991, 7, 581, 253, 827, 499, 1073, 89], [721, 1237, 1151, 463, 377, 979, 893, 119], [1261, 697, 791, 133, 227, 979, 1073, 509], [721, 1357, 191, 403, 827, 1039, 1463, 509]]
Les restes mod p['i] de tous les éléments de chaque pfam['i] sont
pfam[0] tous = 4 (r[0])
pfam[1] tous = 8 (r[1])
pfam[2] tous = 10 (r[2])
...
pfam[11] tous = 39 (r[11])
Au passage j'ai relevé un doublon : 361 figure dans pfam[2] et dans pfam[6]
Bon, je crois vraiment que je vais devoir suivre le conseil que je t'ai donné et ressortit ton fichier Excel pour suivre pas le programme manœuvre après manœuvre bêtement comme une machine, parce que j'en reviens à vouloir savoir le pourquoi... Tant que je n'ai pas intégré la pourquoi, le comment que j'ai sous les yeux me paraît arbitraire alors qu'il ne l'est pas...
Je vais voir comment j'arrange mon après-midi...
@+
PS : je n'avais vu ta modif de 11 h 00 17