re bonsoir
Oui, je sais, tous les j de chaque sous-liste ci-dessus sont dans l'ordre croissant des j%30 : 1 7 11 13 17 19 23 29
Mais ça ne me dit pas qui ils sont.
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
\(j \in P8\) dans la limite:
[0 ; P_i*29] soit au maximum, 15 j pour chaque P
i, afin de cribler les entiers congrus à
2n%Pi, 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
Pi 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,
\(\leqslant\sqrt{2n}\)
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 :
debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
; 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 :
\(\sqrt{600}\) = 24 dans le pire des cas tu as 23*30= 690 très au dessus de n = 300
\(\sqrt{3000}\) = 54 dans le pire des cas tu as 53*30= 1590 A peine au dessus de n = 1500
\(\sqrt{30000}\) = 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...??