Forum de mathématiques - Bibm@th.net

je là copie et je re test  donc ce serra cribleG5 mopd30
résultat :

Donnez la valeur de n = 30k : 24000000
CribleG5 mod30 : Initialisation: 0.32760047912597656 seconds ---
CribleG5 mod30 : Famille de chaque Pi: 0.015599966049194336 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 1.029601812362671 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 0.5616011619567871 seconds ---
On a 1381022 nombres premiers
Appuyez sur une touche pour continuer...

là ça envoie.....LoLLLL

non il ne peut pas y avoir plus de nombres car dans les deux cas tu as 24000000/30 = 800000 nombre[1] ou nbcell = n/30 * 1

ma version python est python- 3.6.4 amd (64bit)-webinstal ; version 3.6.4150.0 du 03 2018

Bonjour
@Yoshi ,voici un comparatif de temps entre l'ancienne version crible mod30 et ta nouvelle version CribleG3 mod30

on peut voir qu'en temps global il y a peu de différence et la limite maxi pour n est la même..

j'ai à peu près compris le rôle de la fonction fam qui remplace l'indice ou la valeur de j (modulo 30) ; ainsi que la fonction jmod30 qui je suppose correspond à p8 [...]..

c'est à dire , qu'un reste R pair , correspondant à R de 2n par p['i] est transformé en R['i] = j impair, en y ajoutant p['i] pour vérifier à qu'elle famille il appartient  et par rapport à sa D_c = [ 1,3,7,9]

  car D_c = '5' n'à pas lieu d'être testé, on peut donc directement ajouter 2*p['i] ..non ? au lieu de faire une division j%5==0 ??

Mais comme les multiples de 3 se terminent aussi par D_c = [ 1,3,7,9]. Est ce que cela serait pas plus facile de faire :
si  j = D_c==1  on teste si j %1 ==0 or j % 11==0 ; si l'un ou l'autre est oui, on passe au suivant en y ayant ajouté 2*pi...

sinon c'est un multiple de 3 et donc on passe au suivant..... ce qui éviterait peut être les divisions par 3 car il y en a pour chaque j, qui se termine par 1,3,7 ou 9 ce qui alourdi le programme....non ?

voila pourquoi il est aussi intéressant de ne travailler que sur une famille, quitte ensuite à modifier les paramètres de la famille pour en choisir une autre dans le programme...on teste uniquement la D_c de la famille en question avec une seule division...par exemple si on a fixée la famille fp = 1  si j = D_c==1 on fait j1%30==0 on le positionne et on crible avec son p['i] , sinon on passe au suivant j += 2*p['i]

puisque l'on a déjà tous les p ératosthène > 5, et leurs reste tel que  :  r.append(2*n % p['i]) ce qui donne :
si R est pair on ajoute p['i] et j = R['i] impair et on commence avec ce couple... si d_c =[3,5,7,9] on incrémente j += 2*p['i] et on passe au suivant.... ...etc

si R est impair donc = j , si D_c =[3,5,7,9] on incr = j += 2*p['i] ; si d_c ==1 on teste, si ok on positionne et on crible;  sinon on incr et on passe au suivant....

Passe un bon week end et merci pour ton aide et pour tout....

j'ai trouvé la blague qui fermait la fenêtre .
à la fin dans la ligne :
os.system(pause) il n'y avait pas les ("pause")

voila pour n = 12000:

Donnez la valeur de n = 30k : 12000
Crible mod30 : Initialisation: 0.0 seconds ---
Crible mod30 : Famille de chaque Pi: 0.0 seconds ---
Crible mod30 : Criblage des 8 familles: 0.0 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---
On a 1230 nombres premiers
Appuyez sur une touche pour continuer...

et tant qu'à faire n=3000 000 000

Donnez la valeur de n = 30k : 3000000000
Crible mod30 : Initialisation: 47.0496826171875 seconds ---
Crible mod30 : Famille de chaque Pi: 34.03925967216492 seconds ---
Crible mod30 : Criblage des 8 familles: 203.14035725593567 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 77.32933592796326 seconds ---
On a 135095831 nombres premiers
Appuyez sur une touche pour continuer...

un dernier n=3420000000 et ensuite je vais voir si je dépasse 3720 000 000

Donnez la valeur de n = 30k : 3420000000
Crible mod30 : Initialisation: 45.0372793674469 seconds ---
Crible mod30 : Famille de chaque Pi: 36.14526319503784 seconds ---
Crible mod30 : Criblage des 8 familles: 222.95559167861938 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 114.53540134429932 seconds ---
On a 153107189 nombres premiers
Appuyez sur une touche pour continuer...

au niveau rapidité on est toujours dans les 6 minutes pour 3 mds, je vais modifier F = j +p['i] *29 au lieu de 30...car je n'ai que les valeurs de j sans supplément ce qui ne change rien.. à piori c'est plus "stable" dans l'exécution...
je vais voir la limite.
ne t'embête pas pour charger pycharm ...Car il faut de toutes façon ne travailler que sur une Famille p8 = ['11'] ou fp = 11 ,par exemple 
ce qui permettra de réduire les recherches D_c ['3','5','7','9']  et j += incr etc etc. 

la limite wile j < f , devrait être:  wile j != %30 == 11  car on travaille famille 11(modulo 30) ..si c'est comme cela qu'il faut l'écrire 
et enlever les lignes qui ne servent plus à rien, ainsi que l'initialisation qui se ferra sur une seule ligne ou colonne...

de ce fait on vérifie la décimale : d_c = '1' et si j 11%30== 0 sinon on passe au suivant  ce qui limitera aussi les calculs, la vitesse et on va plus loin ....etc

et tu m'envoies la facture...par mail...@+

re @Yoshi
je viens de faire dans Pycharm alt ctrl s
cela m'ouvre une fenêtre  écrit en anglais donc je ne sais pas ce que je dois faire ....

je vais copier coller ton indentation je vérifie pour n = 12000 et je met le résultat si ok....
à tout de suite

Bonjour
@Yoshi , je viens de vérifier avec ton instruction : d_c = j%10 et d_c 2%==0: au lieu de ['0','2','4','6','8']:
pour n= 150, effectivement les j = r['i] sont les mêmes ...Conclusion, ils doivent être mal positionnés dans leur famille respective...! pour indiquer les mauvaises valeurs : 31 nombre au lieu de 27. Ou alors il occulte le premier r['i]....?

voici ci-dessous les j pour p['i] = 7 et 2n%p['i] = 6 , d'où : j = 6+7=13 et 13 + 2*7 = 27 ; de plus 13 + 7*29 = 223 , qui est bien le dernier j

de ce fait, le programme doit bien positionner les 8 j afférente à leur famille respective...
on a donc j qui appartient au p8 = [1.7.11.13.17.19.23.29]

soit j = [181.97.41.13.167.139.83.209] le 13, même si il est masqué, il est bien pris en compte par le programme, et placé ligne 0 ou le [1] quatrième famille est marqué [0]. Car le bloc de commande qui vérifie la terminaison:

Positionne aussi à la bonne place le j= r['i], par le quotient, tel que (13 -13)/30 = 0, donc ligne ou cell n° 0 puis p['i] = 7,à partir de cette position,  va cribler c'est à dire marquer d'un[0] tous les 7 nbcell jusquà n/30 = 5 nbcell ...

pour j = 181

  on a (181 - 1) /30 = 6 donc trop grand il ne peut rien marquer pour n = 150 ...ok

Mais par contre, pour p['i] = 13 ; R = 1 et donc j = 1+26 = 27...etc  on aura bien D_c ='1' donc (1 -1) /30 = 0
le [1] nbcell n°0 serra transformer en [0] et 13 va cribler en partant de cette position...

donc voila pourquoi il faut être sûr que les j sont bien positionnés avec la fonction d_c = j%10 ou que

, ne modifie pas la position de départ de j=['i], dans sa famille...car p['i] ne partira pas de la bonne position d'où erreur dans le décompte...des ncell == [1] et des nombres premiers de n à 2n...

Donnez la valeur de N = 30k : 150
27
41
55
69
83
97
111
125
139
153
167
181
195
209
223

pour qu'il n'y ait pas confusion :

p Eratosthène est la liste des premiers > 5 et [tex]<\sqrt{2n}[/tex]
p['i'] est un nombre premier appartenant à p
R est les reste de la division de 2n par p['i']
R['i'] est le R + p['i'] si R est pair, ou R + 2*p['i'] pour R impair , puis on progresse modulo 2*p['i']donc les j = R['i']

On calcule les j jusqu'à la limite < (R + p['i']) + p['i']*30, c'est à dire j + p['i']*30

car sinon si on avait mis  : Wile j < n et bien cela aurait calculer tous les j inférieur à n ce qui est absurde puisque l'on a besoins que de la position de j par Famille, donc des 8 j, un par Famille; pour chaque p['i'] , et ensuite , à partir de cette position c'est p['i'] qui crible jusqu'à la limite n/30 et ce, dans chaque famille; puisque l'on travaille dans les familles de raison 30, sauf la première cellule qui vaut : [1,7,11,13,17,19,23, ou 29]

voici un extrait des j = r['i']  pour n = 150.pour les  P['i'] = {7,11,13,17}  ce qui donne , 15 j, est le 16ème est tout simplement la réitération de j + pi*30
exemple n = 150 on a 2n = 300 et racine de 2n = 17,...,

Pour pi = 7, R= 6, 2n =300, J = 6+7 = Ri = 13 et 13 + 7*30 = 223 qui est le dernier j = ri

le suivant pi = 11 ; R = 3 ; j = 3 + 2*pi = 25 ; et 25 +11*30 = 355 qui est la limite wile j < f ligne 57 du programme.

etc etc  .. pi = 13 ;

c'est ok...
@+

je viens d'essayer c'est pire au lieu de 28 nombre , j'en ai 31 , pou n =150

Donnez la valeur de N = 30k : 150
Crible mod30 : Famille de chaque Pi: 0.0010001659393310547 seconds ---
Crible mod30 : Criblage des 8 familles: 0.0 seconds ---
On a 27 nombres premiers
Appuyez sur une touche pour continuer...

Bonjour Yoshi....
1) pourtant,  je les ai rentrée les balises

  ...??? je vais modifier le message ci-dessus

2) c'est surement un mauvais point pour mon petit fils , je fais ce que je peux pour modifier certaine ligne mais je ne comprend pas Pycharm en plus c'est en anglais...

3)je viens de faire un copie collé de ton programme réindenté dans Pycharme , je lance et ça ne marche pas la fenêtre cmd se ferme directement...
voila ce que donne  avec l'indentation d'avant:

extrait

4) dans mon programme c'est

et non 2n%p
c'est mon copié collé entre les balises code qui m'enlève les

ok je comprend ta surprise .....

5) je recopie le code dans pycharm ci-dessous

ok je viens de vérifier les 

sont bien restés...

7) donc je vais modifier les lignes que tu m'as indiquées...et je fais un test je comprend aussi pourquoi en recopiant ton indentation ça ne marchais pas puisque les

ont été supprimés , d'où ta surprise que ça pouvait fonctionner dans Pycharm alors que non !...

je reviens...voila l'instrucstion ok

Mais cette partie là ci-dessous génère une erreur dans le criblage...je t'ai mis le i devant les r et les p

Bonjour
@Yoshi
voici ce bloc d'instructions qui me pose question:

la commande  while j < n: veut bien dire que l'on ajoute p(i) à J jusqu'à n , et j = r(i)

dans le bloc d'instructions ci-dessus

Mais normalement il ne devrait pas y avoir une autre instruction: 1) tel que on ajoute p(i) jusqu'à d_c == '1' et et on vérifie le (modulo)1%30 ou 11%30 = 0 , ou jusqu'à < n

c'est à dire : while J % 30 == p8[0] , ou < n:

exemple:

Exemple de crible N = 150 , Pi < sqrt 300 = {7;11;13 ; 17 } ; reste R de 300 par les Pi :  R = {6; 3 ; 1; 11} . 150 /30 = 5 cell par Famille.
Pi = 7 et R = 6 , ce qui va donner : 6 +7 = 13 ; → +14 = 27 → +14 = 41→ +14 = 55 → +14 = 69→ +14 = 83→ + 14 = 97→ +14 =111
→ +14 = 125 → +14 = 139 → +14 =153 > n = 150 fini pour Pi = 7 qui ne crible que 5 Famille sur 8.

Pi = 11 et R = 3
3 +( 2*11) → +22 = 47 → +22 → +22 = 91 = 1%30  et (91 -1)/30 = cell N°3

Pi = 13 et R = 1
1 = 1%30 et (1-1)/30 = cell N°0

Pi = 17 et R = 11
11 + 34 → +34 →+34 →+34 > n fin

(« Si on choisit de cribler par Famille et on choisit la Famille 1[30] . Pi = 7 ne marque aucune cellule dans cette famille. Pi = 11 et R =3 , va marquer 91 cell N°3 , puis sort du crible ; Pi = 13 et R = 1 , va marquer la cell N° 0 donc la première le [1] devient [0], puis Pi = 13  sort ; et Pi = 17 et R = 11 ne marquerait que la famille 11[30], et sort »)
   
initialisation
0   1   2    3   4
1 ; 1 ; 1 ; 1 ; 1

criblage
0   1   2   3   4
0 ; 1 ; 1 ; 0 ; 1

A moins que cela se fasse automatiquement dans le programme, c'est à dire que j < n est la limite maximum ....

("Mais je n'arrive toujours pas à modifier pour ne travailler que dans une famille, exemple la famille 1 (modulo 30)...")

je viens de modifier la ligne en question, et cela provoque une erreur pour N = 600 j'ai :98 n primes au lieu de 87, j'augmente de 30 j'en ai 108 au lieu de 91....?
alors qu'avec l'ancienne ligne

j'ai 85 pour N =600 et 90 pour N = 630 soit un écart de 1 par rapport à crible_G(n)...

peut être qu'avec cette ligne :

il faut modifier les lignes d'instruction dessous...???

D'autant que la phrase : # On elimine les restes pairs prête à confusion , car on aurait dû écrire :

Bonjour
@Yoshi ,il se pourrait que l'erreur vienne de cette ligne d'instruction :

car effectivement si le reste R de 2n par P_i est pair on n'a pas besoin de vérifier le modulo de la famille concernée ; mais par contre on part bien de ce reste R auquel on rajoute P_i, et on vérifie si la terminaison correspond bien à l'une des 8 familles concernées et si il est bien congru à P_i modulo 30 pour la famille concernée; ou 1 modulo 30 pour la famille 1 [30].

par exemple , j'ai pris N= 300 et je veux cribler la famille 1[30] . [tex]\sqrt{600} = 24,...[/tex]
les [tex] P_i = 7.11.13.17.19.23[/tex] les [tex]R_i = 5 . 6.2.5.11.2[/tex]
initialisation et criblage de la famille 1[30] cela va nous donner dix nombres [1].
et le criblage va marquer 61 et 271. soit le troisième nombre et le dixième;"qui corresponde à la cellule N°2 et 9"

[tex][1].[1].[0].[1].[1].[1].[1].[1].[1].[0][/tex] extraction, on a bien 8 nombres premiers. (" de n à 2n pour la famille complémentaires à 1[30] soit la famille 29[30]...") qui sont [tex]359.389.419.449.479.509.569.599[/tex] ça on a pas besoins de l'écrire , car on compte que les nombres [1] lors de l'extraction.

mais lors du criblage on voit bien que si les restes R sont pairs, on rajoute P_i si il ne se termine pas par 1 on rajoute ensuite 2*P_i donc impair et si il se termine par 1 on vérifie le "modulo" : qu'il est bien congru à 1[30] ; sinon on continue jusqu'à la limite n = 300...puis on passe au [tex]P_i[/tex] et son[tex]R_i[/tex] suivant...etc

En exemple pour ce cas ; pour [tex]P_i = 11[/tex] et son [tex]R_i = 6[/tex]. On part du reste :

6 + 11 ; 17 +22 ; 39+22 = 61 on vérifie le modulo c'est à dire la ligne de code:

donc ok.

On le place dans sa famille à sa position :
(61-1)/30 = 2 cell N° 2, le troisième [1].

Ensuite on marquera tous les 11[1] jusqu'à la lim N = 300.

Dans cet exemple, on a  que le troisième c'est à dire le N°2, [1] = [0] ;
"car on compte en commençant par 0,1,2,....n"

j'espère que cela correspond bien aux lignes d'instruction du crible_mod30.....???