Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#426 Re : Programmation » crible en python » 26-12-2018 08:24:36
Donc tu penses que même en incrémentant Ai de 30 , pour calculer l'index suivant...de la liste des Ai, ça ne ferait pas tellement gagner de temps ("il faut quand même vérifier que Ai+30 est bien dans la liste Ex 13*19; puis 13 * (19+30) faux out, donc 13*(49+30) > 73 donc out..on passe à Bi suivant =17...
Pourtant lorsque l'on incrémente Ai de 30, on incrémente par la même son idx de Bi appartenant au GM:
EXemple fam = 7: B1 = 11 ; Ai = 17 , idx = 6 ; on aura donc Ai +30 = 47 , donnera idx + 11 =17
Tu as peut être raison, car les deux algorithmes curieusement sont aussi rapides l'un que l'autre...et traduit en C++ , même temps d'exécution pour une même limite N = 128 700 000 000; en 13 secondes...!
l'un calcule des restes que l'on incrémente de 2*pi jusqu'au %30==fam, pour ensuite calculer l'idx....et l'autre calcule les produits (b*a) ....>%30 == fam ; puis idx..., et :
1)_ Criblage de l'idx par de pas $p_i\leqslant\sqrt{2n}$ , pour Goldbach .
2)_Criblage de l'idx par de pas $A_i\leqslant\sqrt{n}$ , pour Ératosthène .
Alors que G, crible avec plus de premiers que É ....? De plus, G crible de l'idx plus petit que celui de E..d'où plus de cellules à marquer...? Comme quoi cela n'influence pas beaucoup le temps d'exécution...Que ce soit en python ou en C++ .
Par contre en C++ par rapport à python il n'y a pas photo....en terme de rapidité * 500 et de limite * 4 ...! Et encore j'utilise Code:bloc qui est en 32 bits sous Windows et non en 64.... ils l'on testé en 64 bits il a mis un peu moins de 60 secondes pour n = 450 000 000 000 ce qui donne pour G de 450 GO à 900 Go...!
Un petit résultat :
Avec Goldbach ; fam 7: nombre de nombres premiers entre 510 000 000 000 et 1020 000 000 000 =
2 331 532 960 en : 55,111 secondes
Avec Ératosthène ; fam 7: nombre de nombres premiers de 7 à : 510 000 000 000 =
2 459 907 472 en : 55,158 secondes
Je les ai testé jusqu'à 1200 GO en 75 secondes chacun à 2 secondes près..
Record ou Pas : sur le site Bibm@th du plus grand nombre de nombres Premiers criblés élémentairement, entre N et 2N ..?
RÉSULTAT Pour N = 3 billions , fam = 11: par Gcrible_mod 30
nombre de premiers criblée de 3 billions à 6 billions = 12 880 098 499 en 734,93 secondes
Par E_crible_mod30 :
Pour N = 3 billions, nombre de premiers 11 mod 30, de 7 à N : 13 542 540 483 en 735,5 secondes
Voila un bon crible de noël , Mr ..YOSHI..
@+ LEG
#427 Re : Programmation » crible en python » 25-12-2018 10:09:06
re :
POUR N = 6000, c'est faisable en 46 opérations , tu peux regarder , je disais que cela allez plus vite, car pour les 8 nombres premiers A, de la liste A, des-que A%30== 7 ,l'index est calculé, A = 31 crible;
Pour le calcule de l'index suivant, on incrémente Aide 30 qui serra obligatoirement =7%30 , et donc re calcule de l'index..de Ai = 61..qui crible, puis Ai+30 = 61 > 73 la boucle B = 7 est fini. i += 1 , B =11
B = 11; "", 11*17 ok idx = 6, 17 crible, suivant : 11* (17+30) idx = 6+11, crible, .suivant 11*(47+30) si par exemple 77 qui n'est pas dans la liste A car il n'est pas premier; pas de problème, on incrémente de 30 Ai et suivant : 77+30 = 107 >73...fin de boucle B pour i = 1, B = 11...!
("C'est à peu près le principe de l'algorithme nbpremier c++ de 2003 , car cette optimisation est justement meilleur que nbpremier")
En inversant les deux listes du programme; les 8 boucles B du GM vont parcourir la liste A des nombres premiers d'Eratosthène
B = [7, 11, 13, 17, 19, 23, 29, 31] n= 6000 Fam =7 nbcell = 6000/30 = 200 à cribler
--------------------------------------------------------------------------------------------
A = 7,,,,11,,,,13,,,,17,,,,19,,,,23,,,,29,,,,31],,,37,,,41,,,43,,,47,,,53,,,59,,,61,,,67,,71,,73]
-----------------------------------------------------------------------------------------------
7 """" """" """" """" """" """" """" 217].,...... ,...... ,...... ,...... ,...... ,......,427..,...... ,...... ,......,
11 """" """" """" 187,......,......,......,......]....., ......,......,.697.,.....,......,......,.......,......,......,.
13 """ """" """" """" 247..,...... ,...... ,].....,...... ,...... ,...... ,...,on saute49.. ,...... ,...... ,...... ,...... ,.....,.....,
17 """" 187 ,..... ,...... ,...... ,...... ,...... ,]..... ,...... 697....,..... ,...... ,...... ,...... ,...... ,...... ,......
19 """" """" 247.. ,...... ,...... ,...... ,...... ,]..... ,...... ,...... 817...,...... ,...... ,...... ,...... ,...... ,...... ,
23 """" """" """" """" """" """" 667.. ,]..... ,...... ,...... ,...... ,...... ,......667... ,...... ,...... ,...... ,
29 """" """" """" """" """" 667.. ,...... ,]..... ,...... ,...... ,...... ,.......667.. ,...... ,...... ,...... ,...... ,
31...217..,.....,.....,.....,.....,......,...... ,..... ,].1147.....,......,......,...... ,...... ,......,2077,.....,.....,
--------------------------------------------------------------------------------------------------------
Ce qui supprime toutes les opérations de calcule: produit et modulo pour tout Ai > 31 .
incrément = 30 : Ai + 30, +30 ...+30k et on peut "aussi" incrémenter l'index de: Bi si c'est plus rapide...
D'où , il n'y a que les 8 boucles GM quelque soit le nombre de Ai, de la liste A .
Ainsi que les 8 opérations au maximum, des Ai <= 31, pour trouver les 8 index et ensuite : Bi * [Ai +30k]
C'est faisable...?
illustration, en partant du carré des nombres premiers Bi de la liste GM :
Exemple : on a choisie fam =1 , i = 0, Bi=7:
7*7, 7*11, (7*13) == 1%30. L’index du couple est 3 ; [7 et 13] vont cribler par pas de 7 et de 13, de 3 → n//30.
Une fois terminé on fait un break et on les incrémente de 30, pour réitérer et continuer avec Bi+30 ; (7+30 , 13 +30)qui sont bien dans la liste des Ai(premiers), (« sinon on augmente de 30 jusqu’à fin de liste des Ai(premiers) donc <= 89. »).
Ce qui donne :(Ai)² = 37*37 , calcul index et criblage, puis 43*43, index et criblage. Break ; on incrémente à nouveau ces deux Ai (37 et 73 )de 30 ; soit: 67*67, index et criblage ; puis 73*73, index , criblage ; fin pour ces deux Familles Bi[30].
On passe à Bi suivant.
Suivant Bi=11 : (11*11) == 1%30 ; index 4 et crible par pas de 11, de 4 → n/30.
Break ; on incrémente Bi de 30 ; soit Ai = 41, produit = 41*41 ; index, criblage,break et on incrémente à nouveau de 30 tant que Ai +30k est <= à sqrt n fixé, soit 89 pour cet exemple.
Donc :71*71 , index, criblage ; fin pour cette Famille Bi[30].
On passe au suivant.
Bi suivant = 17 car la famille Bi = 13[30] a déjà été utilisé et finie….
17*17, 17*19, 17*23 == 1%30 ; calcule de l’index pour le couple (17,23)//30 = 13 le couple va cribler par pas de 17 et de 23 ; de 13 → n/30 , break, on incrémente de 30 : 17 et 23 , produit des carrés, index, criblage fin des deux Familles Bi = 17 et 23 [30]
etc ….etc.
On réitère avec Bi suivant = 19…. etc…jusqu’à la dernière Famille Bi=31[30].
A la fin on fait le total des [1] qui donnera le nombre de nombres premiers : q[n ; 2n].
le programme est un peu plus difficile, mais on supprime beaucoup d'opérations...
#428 Re : Programmation » crible en python » 25-12-2018 08:34:03
Bonjour Yoshi
j'attendais le père noël après 21h30 ...pour qu'il m'apporte ses idées....je te remercie et j'espère que tu vas bien en profiter .
A_)
concernant tes 50 boucles.. ok..Mais je pensais vraiment que c'était plus rapide 8 boucles sur 50 nombres ..! car il y a justement le phénomène qu'après les 8 premiers sur les 50 nombres premiers, il y a de plus en plus d'écart entre ces premiers, de ce fait la congruence du produit %30 ==fam, est plus rapprochée , d'où moins d'opérations lorsque n tend vers l'infini...Sur excel , manuellement je vais plus vite...
B_)
Si c'était faisable, effectivement la sommation finale est automatique..
Mais justement le problème des doublons n'est pas gérable...
n=3000 ; fam = 7 , Pi =7
ok : on a les 1000 [1], j'ai l'index 7,pour Pi = 7; par pas de 7, j'enlève un 1 à chaque pas de 7 et autant de 0 à la place..Sachant que je vais partir de 7 ....>1000 = (993/7) +1, le premier 1 enlevé au départ . J'ai enlevé 141 + 1 [1] . Somme = 1000 -142. ON est d'accord..? sous total = 858.
Pi = 11 pour l'index 6 ; même opération par pas de 11 de 6 à.....> 1000 ; soit :(858 / 11) + 1. 72 [1] d'enlevés... Où sont les doublons parmi ces 72 [1]....Comment tu les vois..? ou comment le programme va le savoir. ..?
Sachant que les doublons vont se répéter en fonction du nombres de pas UNIQUES par Pi...dixit le TFA..("thèoreme fond de l'arith..")..cela revient à prévoir la factorisation unique d'une cellule[1]...Imagine les conséquences....
Il y a un polynôme avec 26 variables de degré 25 ; qui ne prends que les nombres premiers...donc qui élimines les doublons....
tu peux illustrer et faire un essais : j'ai marqué les deux index de départ, [(0)] =7 pour Pi = 7 ; "0" 6, pour Pi =11
111111"0"[(0)]111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)1
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1) la seule chose que l'on sait: c'est que la cellule d'index 6 partagé par 11 *17 se retrouvera dans 187 cell, donc d'index 6 + 187 cellules, avec comme factorisation (7,11 et bien sûr 31) = 5797 et (5797-7)/30 = l'index 193..!
Quel est la factorisation de la cellule X = (7,11, z) le ou les doublons...?
au pif: 9 * 7 = 63 au départ de la 8ème cellule = 71 cellules; moins la cellule 0 =7 , cela fait 70 cellules :
vérification : 70*30 + 7 = 2107 ; 2107/7 = 301; 301 / 11 = Faux... le conjoint de 7 avec 11, c'est 11 + 30 = 41.
cellule 106 ok....(105*30 + 7) est /7/11 et 41.
41 qui a pour index 23 donné par (17*41) // 30 ...c'est ingérable , comme le polynôme schmoldu...à 26 variables...
Je vais regarder de mon côté ce que donne le nombre d'opérations pour 8 boucles et n nombres: avec 6000...
Joyeux Noël cher ami...
Gilbert
@+
#429 Re : Programmation » crible en python » 24-12-2018 08:50:11
Bonjour Yoshi
est ce que tu as essayé d'inverser la boucle : a,b en b,a:
GM=[7, 11, 13, 17, 19, 23, 29, 31] # c'est aussi une liste
premiers=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] # c'est une liste
for b in premiers:
print ("Avec a =",a,end=" ")
for a in GM:
print ((a,b),end=" ") # Affichage des couples (a,b)
print()
de sorte, que c'est B = 7 , qui va parcourir les éléments de a, calculer a%30==fam, puis calculer les index, pour chaque a trouvé, a part cribler ... jusqu'à la fin , on sort de la boucle,] puis on change d'indice i+=1 , B=11...et on réitère...???
il n'y aura que 8 boucles [Bi.....> a]
#430 Re : Programmation » crible en python » 23-12-2018 19:59:00
crochets, accolades, parenthèses...et cannes à pêche ...pour moi je nage....Est-ce que tu le veux transcrit en C++, à la suite des post...?
Ce qui veut dire aussi que pour n > 10: il existe plus de premiers entre 1 et n qu'entre n et 2n.
Et la conjecture de LEG, quelle est-elle ?
la même affirmation que toi..!
En effet les deux algorithmes criblent la même limite de 7 à N : pour compter le nombre de nombres premiers de 7 à N ou de N à 2N
or, il est simple de montrer que l'algorithme d'Ératosthène comptera plus de premiers de 7 à N car il n'utilise que les nombres premiers Pn $\leqslant\sqrt{N}$ pour marquer les multiples n de P .
Alors que l'algorithme de Goldbach, pour la même limite de 7 à N comptera plus d'entiers N congru à 2N modulo P , car il utilise les nombres premiers Pn $\leqslant\sqrt{2N}$ d'où par obligation, moins de premiers entre N et 2N....!
Ce n'est pas une conjecture, mais une évidence....tu ne crois pas....?
c'est aussi pour cela que j'en ai déduit que le nombre de nombres premiers qu'il y a entre N et 2N vaut environ $ \frac{N}{Ln (2N)}$, pour N>= 15; et non $\frac{N}{Ln (N)}$ pour Ératosthène . Cela n'engage que moi, bien entendu..
Si j'utilise le terme de crible ou algorithme de Goldbach, cela vient tout simplement que pour compter le nombre de couples (p,q) qui décompose un entier pair >= 16, en somme de deux premiers p,q on utilise le même crible en ne comptant que les nombres premiers p <=N , qui n'ont pas été marqués par ce crible...Donc :("qui peut le plus peut le moins").....sans aucune prétention, simplement un hobby...
Passe une bonne fin de soirée
@+
#431 Re : Programmation » crible en python » 23-12-2018 19:46:13
ok impeccable, il marche aussi avec les crochets GM= [7,11,13...31]et sans les ( )...donc je laisse comme ça
est-ce que tu le veux transcrit en C++...? je viens juste de le recevoir de Mr Parisse Bernard....ça déménage...
Cela serait bon comme outils sur votre site...non?
#432 Re : Programmation » crible en python » 23-12-2018 18:09:15
bin..j'ai bien fais ce que tu indiques , avec la fonction
for a in (premiers):
for b in (GM):
j = a * b
if j%30 == fam:
dans le programme ci dessous qui marche bien ("et aussi vite que Goldbach de N à 2N "):
from itertools import product
from time import time
def eratostene(n):
n = int(n**0.5)
m = (n-1) // 2
limite=1+n
b = [True]*m
premiers = [2]
for i,p in enumerate(range(3,limite,2)):
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
debut,pas=j,2*i+3
for j in range(debut,m,pas):
b[j] = False
debut=i
for i in range(debut,m):
if b[i]:
premiers.append(p)
p += 2
return premiers[3:]
def demander_N():
n = input("Donnez N: ")
n = int(n.strip().replace(" ", ""))
#n = int(30 * round(float(n)/30))
#print(f"On prend N = {n} (30 * {int(n/30)})")
return n
def lprint(text="", liste=None):
if len(liste) < 250:
print(text + str(liste))
def E_Crible(premiers, n, fam):
start_crible = time()
# On génère un tableau de N/30 cases rempli de 1
crible = n//30*[1]
lencrible = len(crible)
GM = 7,11,13,17,19,23,29,31
# On calcule les produits: j = a * b
for a in (premiers):
for b in (GM):
j = a * b
if j%30 == fam:
index = j // 30 # Je calcule l'index,
# On crible directement avec l'index
for idx in range(index, lencrible, a): # index qui est réutilisé ici...
crible[idx] = 0
#print(j)
total = sum(crible)
lprint("crible:", crible)
print(f"Nombre premiers criblés famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")
def main():
# On demande N a l'utilisateur
n = demander_N()
# On récupère les premiers de 7 à √N
premiers = eratostene(n)
#lprint("premiers:", premiers)
#print(f"nombres premiers entre 7 et n: {len(premiers)}")
start_time = time()
# On crible
E_Crible(premiers, n, 7)
temps = time()-start_time
print(f"--- Temps total: {int(temps*100)/100} sec ---")
main()
résultat :
====== RESTART: E:\executable algo P(30)\E_Crible_ gty_modifié mod30.py ======
Donnez N: 300 000 000
Nombre premiers criblés famille 7 : 2031596 ----- 1.21
--- Temps total: 1.23 sec ---
>>>
et avec ton ancienne version que j'ai posté hier :
résultat :
======= RESTART: E:\executable algo P(30)\CRIBLE_Eratosthène_Mod30.py =======
Donnez la valeur de n = 30k : 300 000 000
Phase d'initialisation: 0.09360027313232422 seconds ---
Bloc S2_s3 : 1.0608017444610596 seconds ---
Extraction des premiers de 7 à n : 0.07800006866455078 seconds ---
** 2031596 nombres trouvés en 1.2324020862579346 secondes **
>>>
#433 Re : Programmation » crible en python » 23-12-2018 15:25:57
Je suis bien d'accord avec toi sur le groupe multiplicatif, et GM ...
car à l'époque de nbpremier xin 32 on ne se sert que de GM qui est un groupe multiplicatif, où en fonction de la fam choisie, on multiplie bien les 8 nombres entre-eux pour calculer l'index des couples qui vont cribler, extraire les nombres premiers > 31, qui vont cribler à leur tour...etc etc ...je ne suis pas rentrer dans les explications de ce crible C++ ...voila...
Bien sûr que mes explications sont lourdes...donc mal comprises pour un matheux...d'où je ne sais pas comment je dois t'écrire
GM {7,11,13,17,19,23,29,31} ,
30k+p avec p∈[1,7,11,13,17,19,23,29] et k>= 1...
Là, avec GM, le 1 a sauté, remplacé par le 31...
Bien sûr , 31 à la place de 1..
Ce que j'ai compris quand même, c'est comment écrire GM pour le faire fonctionner dans la fonction...
GM = 7,11,13,17,19,23,29,31
sans accolade..et autre...car erreur list...!
Je viens aussi de rectifier mon erreur d'inattention, c'est bien :
for a in (premiers):
for b in (GM):
#434 Re : Programmation » crible en python » 23-12-2018 15:01:08
j'ai bien écrit avec ta fonction et ta version #v.6.2#:
# FAMILLES POUR CHAQUE Pi
start_time = time()
for i,pi in enumerate(Primes_init):
for b in (GM):
j = pi*b
if j%30 == 1: # chan
dans le Gcrible sur lequel tu travaillais avant hier :
avec ta première fonction que j'ai mise :
def E_Crible(premiers, n, fam):
start_crible = time()
# On génère un tableau de N/30 cases rempli de 1
crible = n//30*[1]
lencrible = len(crible)
GM = 7,11,13,17,19,23,29,31
# On calcule les produits: j = a * b
for a in (premiers):
for b in (GM):
j = a * b
if j%30 == fam:
index = j // 30 # Je calcule l'index,
# On crible directement avec l'index
for idx in range(index, lencrible, a): # index qui est réutilisé ici...
crible[idx] = 0
#print(j)
total = sum(crible)
lprint("crible:", crible)
print(f"Nombre premiers criblés famille {fam} : {total} -
suite à ton exemple et tes explications tu ""as dit"" que ce sont les éléments B qui criblent en partant de leur index...
Donc maintenant, B = premier= 7,11,13,17,19,23,29,et 31 ; va bien parcourir les éléments a qui vont cribler en partant de l'index..Non?
ton exemple du post page 14
a = 7
(31, 7)a = 11
(47, 17) (17, 6)a = 13
(19, 8)a = 17
(41, 23)a = 19
(43, 27)a = 23
(29, 22)
#435 Re : Programmation » crible en python » 23-12-2018 14:10:36
excuse moi pour a et A et pour Ai comme les Pi
Et là :
Pourquoi commencer par
for i,b in enumerate(GM):
et ensuite
for a in premiers[i:]: ?
Pourquoi cette inversion subite, par rapport à tout ce qui a précédé ?
par ce que c'est comme ça que le programme fonctionne maintenant..
avec ta fonction que tu m'as écrit..
tu peux le vérifier ; Ai est un élément premier de la liste eratostene....
D'ailleurs j'ai déjà fait l'inverse et le résultat est archi faux.
car dans cette version, ce sont les A i = n qui parcourt les 8 éléments de B= GM (''que l'on m'avais dit en 2003 groupe multiplicatif..maintenant je peut l'appeler comme tu veux...")
quelque soit A qui va parcourir B, il aura toujours son index et il n'a pas besoin de parcourir tous les élément de B(premiers) équivalent aux éléments A(premiers)
#436 Re : Programmation » crible en python » 23-12-2018 13:14:58
Faut pas courir partout : qui trop embrasse mal étreint !...
oui mais ... il court il court le furet, le furet du bois joli...Tu as entièrement raison méaculpa...
C'est exactement comme cela que j'ai modifié la fonction et qui marche dans les deux cribles, comme tu as pu le constater avec les résultats..
Concernant ma question: en C++ on peut faire partir les Ai, les uns derrière les autres...est ce qu'en python c'est faisable aussi car on gagnerait du temps:
On a donc le [GM avec ses 8 B indicés de 0 à 7]
i= 0, B=7
i= 1 , B=11
i= 2, B=13
i= 3, B= 17
i= 4 , B=19
i= 5, B=23
i= 6, B=29
i= 7 , B=31
On a donc :
for a in (premiers):
for b in (GM):
j = a * b
if j%30 == fam:
i = 0 , B= 7 : va parcourir les $A_i$ qui sont les $a$ = premiers extrait par Ératosthène, du début à la fin,
B =7 part cribler puis il fait partir tous les $a$ de l'index j%30==fam calculé , les uns derrière les autres lorsque le dernier $a$ à criblé par pas de $a$,..
on passe à l'indice suivant i+1
i =1,B = 11: part cribler de l'indexe j%30==fam puis va parcourir les $a$ du début à la fin, qu'il fait partir de leur index j%30==fam par pas de $a$...etc .. indice i+1 = 2 suivant, B=13
i = 2, B=13.... on réitère
EXemple pour Fam =7 et n =3000
B = 7 , $ j = a*b$ 7 et 31 , j ==7%30 ils ont pour index de départ, l'index j//30 == 7 ,...7 part cribler par pas de 7 et fait partir 31 pas de 31, il n'y en a pas d'autre car 61> 53 . on passe à l'indice suivant i+1 , B = 11
B=11 , va faire partir 11*17==7%30, ils ont l'index 6; 11 et 17 partent cribler , puis B=11 continue, parcourt les $a$ il va faire parti 47==7%30 de l'index 17...> n/30] fin pour B= 11, indice suivant B = 13, on réitère ...etc
à la fin des 8 indices B , on fait la somme des [1] tous les $a$ ont criblé la fam 7 de leur début d'index...!
Qu'est ce que tu en penses...? pour accélérer le programme...
Pour t'avoir fais galérer pour rien...et mal compris, où je t'envoie les bouteilles et le panier garni...ou autre...! car le réveillon va être fini....
#437 Re : Programmation » crible en python » 23-12-2018 11:42:18
D'accord, je n'avais pas compris le sens de ta question...OK
D'où maintenant, il suffit d'utiliser B = le GM avec ses 8 premiers...Pour effectivement éviter cette erreur , en passant en revue toute la troupe de B...
Question :
si c'est le GM i = 0 , B = 7, qui parcourt la liste A, mais à chaque index, break, A part cribler par pas de A , puis GM inidce i = 0 pour B =7, continue dans la liste A ,j%30, A crible par pas de A,..etc
Ensuite on change d'indice i = 1 pour B= 11....> A = [7....à 53]
Ets ce que cela serait plus rapide....?
#438 Re : Programmation » crible en python » 23-12-2018 08:58:20
Bonjour Yoshi:
voici les résultat : Fam = 1, 7 pour n = 3 000 000
Après avoir remis la def eratostene à n = int(n**0.5) et modifié ta première fonction avec le GM.
GM = 7,11,13,17,19,23,29,31.
== RESTART: E:\Documents\Conjecture de Goldbach\CRIBLE_Eratosthène_Mod30.py ==
Donnez la valeur de n = 30k : 3 000 000
Phase d'initialisation: 0.0 seconds ---
Bloc S2_s3 : 0.031200170516967773 seconds ---
Extraction des premiers de 7 à n : 0.0 seconds ---
** 27042 nombres trouvés en 0.031200170516967773 secondes **
>>>
== RESTART: E:\Documents\Conjecture de Goldbach\CRIBLE_Eratosthène_Mod30.py ==
Donnez la valeur de n = 30k : 3000000
Phase d'initialisation: 0.015599966049194336 seconds ---
Bloc S2_s3 : 0.031199932098388672 seconds ---
Extraction des premiers de 7 à n : 0.0 seconds ---
** 27137 nombres trouvés en 0.04679989814758301 secondes **
>>>
Programme :version #v.6.2# modifiée pour Eratosthène ...qu tu peux surement optimiser avec ta deuxième fonction dans cette version..
from time import time
from os import system
from collections import OrderedDict
## V. 6.2 ##
def eratostene(n):
n = int(n**0.5)
m = (n-1) // 2
limite=1+n
b = [True]*m
premiers = [2]
for i,p in enumerate(range(3,limite,2)):
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
debut,pas=j,2*i+3
for j in range(debut,m,pas):
b[j] = False
debut=i
for i in range(debut,m):
if b[i]:
premiers.append(p)
p += 2
#print(premiers)
return premiers[3:]
def E_CribleG3Y_mod30(n):
# INITIALISATION
global nombres,nbcell
start_i= time()
Primes_init = eratostene(n)
nbcell = n//30
nombres = []
GM = 7,11,13,17,19,23,29,31
for i in range(1):
nombres.append([1]*nbcell)
P8 = {1:0} # changer le paramètre pour une fam fxée
s_1=time()-start_i
print("Phase d'initialisation: %s seconds ---" % s_1)
# FAMILLES POUR CHAQUE Pi
start_time = time()
for i,pi in enumerate(Primes_init):
for b in (GM):
j = pi*b
if j%30 == 1: # changer le paramètre pour une fam fxée
fam = P8[1] # changer le paramètre pour une fam fxée
debut_index = j//30
Nombres_fam = nombres[fam]
for index in range(debut_index, nbcell,pi):
Nombres_fam[index] = 0
s_23=time()-start_time
print("Bloc S2_s3 : %s seconds ---" % s_23)
#print(Nombres_fam)
# CALCUL DES NOMRES PREMIERS de 7 à n
start_time = time()
total = 0
for sous_liste in nombres:
total += sum(sous_liste)
s_4=time() - start_time
s=s_1+s_23+s_4
print("Extraction des premiers de 7 à n : %s seconds ---" % s_4)
return total,s
n = int(input("Donnez la valeur de n = 30k : "))
nbr,s = E_CribleG3Y_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")
A+ gilbert
#439 Re : Programmation » crible en python » 22-12-2018 14:59:42
Après rectification du post 344 :
A = 7 11 13 17 19 23 29 31 37 41 43 47 53] 59 61 67 71 73
n= 6000 Fam =7 nbcell = 6000/30 = 200 à cribler
pfam GM ({7, 11, 13, 17, 19, 23, 2931})
A ] ..GM = [7 11 13 17 19 23 29 31]
=
Pi ].........................................................
7 49 77 91 119 133 161 203 217 idx=7
11 77 121 143 187 idx=6
13 91 143 169 221 247 idx=8
17 119 187 idx=6
19 133 209 247 idx=8 ( 36 opérations )
23 161 253 299 391 437 529 667 idx=22
29 203 319 377 493 551 667 idx=22
31 217 idx=7
....................................................................
37 259 407 ,, ,, ,, ,, ,, 1147 idx=38
41 287 ,, ,, 697 idx=23
43 301 473 559 731 817 idx=27
47 329 517 idx=7 (+ 19 opérations pour n = 3000)
......................................................................
53 371 583 689 901 1007 1219 1537 idx=51
59 413 649 767 1003 1121 1357 idx=45
..............................................................
61 427 idx = 14
67 469 ,, ,, ,, ,, ,, ,, 2077 idx=69
71 497 ,, ,, 1207 idx=40
73 511 803 ,, ,, 1387 idx=46 fin pour n = 6000 ; en 86 opérations
Donc un total de 55 opérations. et de 86 pour n = 6000
chaque indice i relatif à A, va parcourir et mutiplier les éléments du de la pfam = GM
voila ..
ton idée ..?
Il me semble que cela doit être rapide comme temps d'exécution...
Plus vite que GOLDBACH...,? Où , c'est fonction , du nombre d'incrémentations par addition dans chacune des pfam et de leur nombre de divisions pour vérifier l'égalité du %30 avant de cribler..
Par contre le criblage est plus rapide pour chacun des pi dans Eratosthène..Exemple: pi =7 et Fam = 3000
Dans E :7 part de l'index 7 avec 8 opérations
Dans G : 7 par de l'index 4 avec 10 opérations....
Ta fonction ci-dessous est juste, mais c'est à cause de l'inversement de ta liste B qu'il y a erreur de résultat...!
nbpremiers,lp = len(premiers),len(premiers)-1
for i,a in enumerate(premiers):
ii=i-1
for k in range(lp,ii,-1):
j = a * premiers[k]
if j%30 == fam:
index = j // 30 # Je calcule l'index,
break
# On crible directement à partir de l'index
for idx in range(index, lencrible, a): # index qui est réutilisé ici...
crible[idx] = 0
si tu utilises la liste B = GM = ({7, 11, 13, 17, 19, 23, 29, 31}) tu verras que le résultat est juste, sans inverser...
pour n=30 000 fam =7 tu dois avoir 407 premiers.
Regarde ton #post 335: avec tes explications....! et ton exemple, indice i=0 et i=1:
(11, 53) (11, 47) [color=#A605F9](11, 43)[/color] (11, 41) (11, 37) (11, 31) (11, 29) (11, 23) (11, 19) (11, 17) (11, 13) (11, 11
Pourquoi penses tu que la 7eme cellule de l'indice 6 est toujours marqué [1] au lieu de [0]...? ci-dessous:
Donnez N: 3000
crible:[1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1,....
quel est la valeur de cette cellule...???
qui aurait dû marquer cette cellule avec son conjoint = ??? et pourquoi ce n'est pas marqué..???
c'est la même erreur que dans mon post supprimé .....!!!
Donnez N: 6000
crible:[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1.... Tiens cela s'aggrave avec n = 6000....maintenant il y a l'indice 6 et 7 qui sont marqué d'un [1] au lieu de [0]..
cela a le mérite, que ta fonction marche marche très bien , mais c'est ta liste B inversée, qui met la zone : solution tu prends la liste A dans le sens normale, la liste B deviens liste GM qui serra toujours la même quelque soit n et Fam..!
et c'est la liste A, indicée qui parcourt le GM ""liste B"" :
( 7, 7) ( 7, 11) ( 7, 13), ( 7, 17) ( 7, 19) ( 7, 23) (7,29), (7,31) .
(11,7) (11,11) (11,13) (11,17) .
# Sachant qu'ils ne sont pas tous calculés, puisque maintenant le 1er a*b %30=fam était, avant le 2nd, et dès qu'il a été trouvé, je calcule l'index et en dessous, aligné, j'ajoute : break qui force la sortie de la boucle b.
Il sort donc dès les calculs avec 11*47 effectués.
et 11*17 ...? qui marque l'indice 6 = 187....?
#440 Re : Programmation » crible en python » 22-12-2018 09:07:32
Bonjour Yoshi
1) si ... j'ai bien intégré comment cela fonctionne mais il y a trop d'opérations inutiles..
2)
Lorsque j'ai Pfam :[11111111]
cela ne peut pas être les 8 fam par colonne que tu criblerais :
sauf si par colonne tu cribles :nbcell = n//30 *[1].Ce qui serra faux : si tu parcours les 8 colonnes en partant d'un index..ok?
car un index c'est pour aller cribler dans une et une seule fam donc une colonne....ou une ligne de nbcell.
à titre d'exemple pour fam 0 = 1 voila le résultat:
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
2999911
>trouvé à la position:
27042
Au lieu de
Famille 1 : 24551
3) les pfam, c'est pour y calculer les produits, comme tu le faisais avec les reste Ri += 2pi ....> tant que j%30 != fam...d'accord.?
[pfam] pour l'indice i=0 , A = 7 [7*7, 7*11, 7*13, 7*17 , 7*19, 7*23 , 7*29 et 7*31] ça ne peut pas aller plus loin que 8 produits..! Alors que la liste Bpi contient 13 pi ou plus en fonction de n...car si je continue et bien 7*37 == 19%30 comme 7*7..ok
4)******************************************************
reprise et modification du #post 344 ci-dessus: il y a une erreur
Donc retour vers le passé, avec ta liste A mais sans avoir besoin de l'inverser....Car cela ne commettra pas mon erreur... Ni celle que tu rencontres et qui donne une résultat FAUX.
....
Car comme moi, tu ne vas pas redescendre assez bas, pour marquer une cellule d'un [0] et garder le [1]....par exemple, dans le cas de n = 6000 ce que je viens de vérifier...! puis, qui s'aggrave pour des limites n plus grandes.....
***********************************************************************
5) le fonctionnement à l'envers fais gagner des opérations ....mais fausse le résultat.!
peut on dans ta version, n'utiliser que le groupe de Multiplications GM = [pfam].....?
GM ={7,11,13,17,19,23,29,31,} au lieu de la liste B inversée....tu verras que tu ferras moins d'opérations et avec un résultat juste..!
[la liste B = liste du groupe de multiplications GM et bien sûr Liste A erastostene < sqrt de n .] la pfam contiendrai le GM...!
la liste A normale, parcourt le GM, calcul l'index et pi = A et non B part cribler...! puis indice suivant i+1 = A1
A1=7, parcourt pfam ({7,11,13,17,19,23,29,31,}) ...> 7%30. calcule de l'index, A1 part cribler par pas de A1 de l'index à N/30 = Famille 7 par exemple. pour n= 3000. On réitère avec A2 et pfam
A2=11, parcourt pfam ({7,11,13,17,19,23,29,31,}) ...> 7%30. calcule de l'index, A2 part cribler par pas de A1 de l'index à N/30
A3=13, parcourt pfam ({7,11,13,17,19,23,29,31,}) ...> 7%30. calcule de l'index, A3 part cribler par pas de A1 de l'index à N/30
etc...etc on réitère..
D'où pas besoin de manipuler la liste A , comme tu le pensais pour éviter les ennuis de python...
Mais pour info :
ça c'est une pfam[1.1.1.1.1.1.1.1] 8 opérations de multiplications au maximum ou groupe GM.Eratosthène. #pour Goldbach pfam, [1.1.1.1.1.1.1.1.1.1.1.1.1.1.1] 15 au maximum, mais seulement 8 appartiennent à une Fam; car il y a les multiples de 3 et de 5 lorsque l'on incrémente par addition += 2p1 ...> %30 = Fam
#441 Re : Programmation » crible en python » 21-12-2018 16:38:35
Re Bonjour :
1 ) après réflexion sur la fonction :
nbpremiers,lp = len(premiers),len(premiers)-1
for i,a in enumerate(premiers):
ii=i-1
for k in range(lp,ii,-1):
j = a * premiers[k]
if j%30 == fam:
index = j // 30 # Je calcule bien un index, non ?
break
# On crible directement avec l'index
for idx in range(index, lencrible, a): # index qui est réutilisé ici, non ?
crible[idx] = 0
2 )
Sur mon Post au dessus en expliquant d'utiliser les [Pfam] mais sans inverser la liste de premiers pour calculer les produits =J ; en optimisant le nombre d'opérations...
Tu as fait une remarque qui à fait tilt...
Ci-dessus ce sont des couples (b, index) pour fam =7 et n=3000
il y aurait encore plus simple : DESOLE MAIS L'ALGO SERRA FAUX après controle...cétait trop simple je n'ai pas vue l'erreur§
on appelle la liste a = prime les premiers eratostene qui vont multiplier les éléments premiers de la liste b eratostene aussi
pour chaque indice i : on rapplle la liste B , mis à jour déduite des éléments b = premiers qui sont aller cribler
i=0
a = 7 : 7*7,7*11,7*13,7*17,7*19,7*23,7*29,7*31//30
(31, 7) premier ou b = 31, index =7 b va cribler de 7 à n//30 par pas de 31
i=1 on rappelle liste b - {31}
a = 11 :11*7, 11*11,11*13,11*17 //30
(17,6) ... b = 17, index =6 b va cribler de 7 à n//30 par pas de 17 . on réitère :
i=2 rappel liste b - {31,17}
a = 13 ; 13*7, 13*11,13*13,,13*19//30
(19, 8) b =19 , index = 8 b va cribler de 8 à n//30 par pas de 19 . on réitère :
i = 3 rappel liste b - {31,17,19}
a = 17 : 17*7,17*11//30
(11,6) b =11 , index = 6, b va cribler de 6 à n//30 par pas de 11 . on réitère :
i=4 rappel liste b - {31,17,19,11}
a = 19 :19*7,, 19*13//30
(13,8) b =13 , index = 8, b va cribler de 8 à n//30 par pas de 13 . on réitère :
i=5 rappel liste b - {31,17,19,11,13}
a = 23 : 23*7,,,,,23*23, 23*29//30
(29, 22) b =29 , index = 22, b va cribler de 22 à n//30 par pas de 29 . on réitère :
i=6 rappel liste b - {31,17,19,11,13,29}
a = 29 : 29*7,,,,, 29*23//30
(23, 22) b =23 , index = 22, b va cribler de 22 à n//30 par pas de 23 . on réitère :
i=7 rappel liste b - {31,17,19,11,13,29,23}
a = 31 : 31*7//30
(7, 7 ) b = 7 , index = 7, b va cribler de 7 à n//30 par pas de 7 . on réitère :
i = 8 rappel liste b - {31,17,19,11,13,29,23,7}
a = 37 : 37*37, 37*41,37*43, 37*47,37*53...stop on réitère
''pas d'index, car il serait avec 61 >53 aucun problème b = 31 a déjà marqué la cellule [0] = 31*37 index = 7+31 comme si il avait criblé !
i = 9 rappel liste b - {31,17,19,11,13,29,23,7,37}
a = 41 : 41*41, 41*47//30
(47, 64) b = 47 , index = 64, b va cribler de 47 à n//30 par pas de 47 . on réitère :
--------------------------------------------------------------------------------------
i=10 rappel liste b - {31,17,19,11,13,29,23,7,37,47}
a = 43 : 43*43,43*47,43*53, pas dindex ,cellule marqué [0] par pas de 19 donc ok
i=11 rappel liste b - {31,17,19,11,13,29,23,7,37,47,43,47}
a= 47 : 47*47,47*53....idem cellule déjà marqué par 41 ok
i= 12 rappel liste b - il ne reste dedans que 53
a = 53 :53*53 ok fin du crible somme des [1]
On a fait 39 multiplications et calculé 9 index.. pour 8 criblages sur 13 ...un peu moins que ci dessus avec les Pfam mais 12 manipulations dans la liste b....aucune dans la liste A .... et à chaque fois que l'on rappelle la liste b elle se réduit de nb premiers à 1 seul il n'en reste qu'un ...c'est le Hyghlander....
Est ce plus simple... par rapport à l'explication ci dessus il me semble que cela serait plus long que d'appeler tes Pfam... Ce qui évite d'enlever à chaque fois un nombre premiers b dans la liste ce qui prend du temps...???? pour un gain d'opérations....mitigé
voila le déroulement de l'algorithme..Eratosthène mod30...selon ce principe...
@+
#442 Re : Programmation » crible en python » 20-12-2018 14:20:25
RE (je n'inverse pas...:)
1 ) le morceau comme je te l'ai dit il ne fonctionne pas du tout dans ta version #v.6.2# de plus il faudra les Pfam en principe .
2) on parle du même index , Mais que l'on utilise différemment.
j'utilise un index commun à : a et B explication au dessus #post 335 ce qui fait au maximum 42 opération , pour n = 3000; fam = 7
ton idée, c'était les Pfam dans Goldbach... et bien c'est la même...!
pour l'indice i = 0 , relatif à : a= 7 et bien Pfam indice 0..
je l'appel, je met dedans [(7, 7) (7, 11) (7, 13) (7, 17) (7, 19) (7, 23) (7, 29) (7, 31) = 7%30]
calcul de l'index de pfan i = 0 pour a et b
7*31 // 30 =7
a part cribler par pas de 7 de 7 à n/30 ; puis b par cribler de 7 à n/30 par pas de 31 .
puis on réitère avec i+1 = 1 pour Pfam =1 et a = 11
i = 1
je l'appel, je met dedans [(11, 11) (11, 13) (11, 17) = 7%30]
calcul de l'index 11*17 / 30 = qui est bien l'index 6 mais pour 11 et 17
a part cribler par pas de 11 de 6 à n/30 ; puis b par cribler de 6 à n/30 par pas de 17 .
puis on réitère avec i+1 = 2 pour Pfam =2 et a = 13
i = 2 , Fam =2 a =13
[(13, 13) (13, 17) (13, 19)]
index pour a et b = 13*19//30 = 8
a part cribler par pas de 13 de 8 à n/30 ; puis b par cribler de 8 à n/30 par pas de 19 . etc etc..
etc etc
toi: tu continu dans ta boucle i = 1 pour a= 11 pour extraire 47 , index 17..moi non, j'ai fini la boucle à 11*17; car c'est 41 qui va calculer l'index de 47
on arrive à i = 9 fam = 9 pour a = 41
[(41, 41) (41, 43) (41, 47)]
index pour a et b = 41*47//30 = 64
a part cribler par pas de 41 de 64 à n/30 ; puis b par cribler de 64 à n/30 par pas de 47 .
**********fin des boucles et du crible soit 44 opérations..****
car tous les a c'est à dire tous les premiers ont criblés, ils ont fait partir leurs conjoint B ...!
d'où i = 10, et 12 sont inutile....!
combien d'opération sans utiliser les Pfam...? 47 de plus ..
Si tu penses (" ce qui m'étonnerait car tes versions avec les Pfam sont très rapides") : que même en faisant plus d'opérations sans utiliser les Pfam c'est plus optimisé.......Alors pas de problème .....reste plus qu' a le paramétrer pour qu'il fonctionne avec le bon résultat.
De plus dans ton système ce qui risque de se produire ...tu vas te retrouver avec l'indice i=0 puis 1 = 1....avec moult opérations ...
au lieu de 8 par Pfam et indice, comme dans Goldbach , amuse toi à vérifier...c'est simple le GM que j'utilise dans nbremier il ne contient que 8 terme soit 4 multiplications ou 6 par fam...
Dans Godbach comme tu as pu le voir au maximum 8...!
#443 Re : Programmation » crible en python » 20-12-2018 12:02:53
Bien sûr , qu'ils sont égaux c'est pour cela que je te met les exemples ...mais tu n'as pas fais attention au déroulement de l'algorithme...
Soit pour n=3000 et l'indice de i = 2
Pour fam=7
a=11, b=17
j=a*b = 187
j%30 = 7 ? oui
donc index= j//30=187//30=6
EXACTEMENT...Mais POUR 11 et aussi 17 l'index est commun..à a et b..!
regarde mon tableau je déroule l'algo :
je fais partir 11, puis retour et c'est 17 qui par de l'index 6 par pas de 17 tu es bien d'accord ...
Où arrive t'il ..? cellule ((17*41) -7) /30 = cellule 23....et ce n'est pas un index ok ..etc il crible.. ..mais on s'en fou , et retour i+1 = 2
Peut être que ce que tu n'as pas vu, ne connaissant pas parfaitement l'algo ce sont toujours les petit Pi qui font partir leur Conjoint b.
D'où rassure toi, c'est 41 qui va faire partir 47 à l'index 64...! et non pas 11.
de ce fait tu peux arrêter les multiplications pour a = 11 de l'indice 1...!et passer à l'indice 2
Pour moi: à l'indice i = 1, relatif à pi = 7; aura : a = 7, b = 31, a*b = 217 index 7: pour 7 et 31 break : ils partent cribler tous les deux de cet index puis retour à l'indice suivant i = 1...! que l'on vient de voir..
l'indice i = 2 , relatif à pi = 13....13*13,13*17,13*19 j= a*b = 247 ,j%30==7 , index de 13 et 19 break , ils partent cribler , et retour 13 a fini les multiplication de son indice 2 . Donc: retour à l'indice i+1 = 3 ...
relatif à 17 qui a déjà criblé par contre il faudrait qu'il fasse partir b donc :
17*17,17*19,17*23, 17*29,17*31,17*37 , 17 *41 tu connais, on vient de le voir ça devient effectivement l'index = 23 et bien comme 17 à déjà criblé on fait partir son conjoint 41 de l'index 23.break , retour à l'indice i+1 = 4
relatif à 19...etc
je t'avais mis le tableau de déroulement de fam = 7...tu as dû zapper avec tous ça... et ne pas faire attention que par indice i et i+=1 il n'y a toujours qu'un couple a et b qui partent cribler ou un seul dans le cas d'un a² et b n'est que le conjoint... d'où le produit a *b = 7%30 , donne le break et la fin des multiplication quelque soit l'indic i relatif à Pi n < Pin+1....
#444 Re : Programmation » crible en python » 20-12-2018 08:13:00
RE suite de ton #post 335 ci-dessus et de mes explications :
voila pour l'instant: ce qui serait très intéressant suite à ton tableau sans inversement 30 opération Fam = 1% 30:
i = 0
(7, 7) (7, 11) (7, 13) on a l'index 3 pour 7 et 13 ; break 7 et 13 partent cribler..retour à l'indice suivant sans continuer sur cet indice i=0
i = 1
(11, 11) on a l'index 4 pour 11 ; break 11 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 2
(13, 13) (13, 17) (13, 19) (13, 23) (13, 29) (13, 31) (13, 37)) on a l'index 16 pour 13 et 37 ; break; 37 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 3
(17, 17) (17, 19) (17, 23) on a l'index 13 pour 17 et 23 ; break 17 et 23 partent cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 4
(19, 19) on a l'index 12 pour 19 ; break 19 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 5
(23, 23) (23, 29) (23, 31) (23, 37) (23, 41) (23, 43) (23, 47) on a l'index 36 pour 23 et 47 ; break 47 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 6
(29, 29) on a l'index 28 pour ; break 29 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 7
(31, 31) on a l'index 32 pour 31 ; break 31 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 8
(37, 37) (37, 41) (37, 43) on a l'index 53 pour 37 et 43 ; break seul 43 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 9
(41, 41) on a l'index 56 pour 41 ; break 41 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 10
(43, 43) (43, 47) (43, 53) pas d'index..ok car 43 devrait faire partir 37+30= 67 < 53...d'accord. indice suivant i +=1
i = 11
(47, 47) (47, 53)on a l'index 83 pour (47,53) ; break , 53 part cribler..retour à l'indice suivant i= +1 sans continuer sur cet indice
i = 12
(53, 53) et pas d'index...
FIN résultat...!
1) moins d'opération, les pi partent de plus en plus loin ; donc accélération du criblage car moins de [1] à remplacer par [0]..
2) ce sont les plus petits pi qui font partir leurs conjoints supérieur , d'où moins d'opérations au lieu de continuer des opération dans l'indice en cour....c'est simple à vérifier...on supprime 82% d'opérations...
.....c'est presque la méthode , mais en plus optimisé que: nbpremier C++, traduit en python...car en C++, c'est le GM qui fait des break et des aller retour, pour faire partir leur conjoints premiers augmenté de 30k à chaque boucle du GM...
#445 Re : Programmation » crible en python » 19-12-2018 22:39:54
fais ATTENTION dans la version que j'ai copié au post 315, page 13 , tu verras la def eratostene est paramétré pour
n = int((2*n)**0.5)
si on met n=int(n**0,5) ce qui doit être le cas et bien le résultat est faux...???
Probablement à cause de l'indexation...
Vers la fin les pi ne peuvent plus être indexés , ce que je t'ai signalé, lors de ton exemple avec le tableau des multiplications pour cribleN°1 et crible N°2
@Yoshi
Supposons l'existence de 2 index calculés :- sont-ils égaux ? si oui, alors à quoi sert d'en calculer 2 ?
1) bien sûr qu'ils sont égaux ; 2) on perd du temps dans le criblage.
- s'ils sont différents, pourquoi dans ce cas ne traiter que le dernier ? Et à quoi a servi de calculer le premier ?
1) les index ne sont pas différent par couple (a*b) mauvaise interprétation ;
2) erreur on doit calculer l'index commun au couple (a * b) afin qu'on les range puis break on continu dans l'indice !
on change d'indice i ; pour calculer les produits%7 de l'indice i +=1. ... l'index du couple ..., break ! on range l'index du couple ou d'un seul..on continue, on change d'indice ( i+1) on réitère ..lorsque l'on a l'index des 13 premiers on par cribler..
- ils sont peut-être différents mais les cribles qu'on obtiendraient seraient-ils les mêmes ?
1) non ! ils ne sont pas différents , le Point de départ du criblage est le même pour (a, b) même index de départ...!
Et question subsidiaire, pourquoi ces cribles seraient-ils les mêmes ?
les deux criblage ne peuvent être les mêmes pour un même point de départ..! le nombre de pas est différent !!
ton exemple crible N° 1 pour 11 * 17:
False
[1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1]
l'index 6, EST pour 11 et 17 ! suite à cette erreur il manque le criblage de 17 que je fais en bleu 0... il n'y a donc pas de crible N°2.....
Ce qui obligatoirement, a pour résultat de limiter encore les multiplications de l'indice en question...de ton exemple :
( 7, 53) ( 7, 47) ( 7, 43), ( 7, 41) ( 7, 37) ( 7, 31) ...donc calcule de l'index commun de 7 et 31 ..break on change d'indice..
une fois le nombre d'index obtenu pour chaque premier par indice i ils criblent , break on passe à l'indice suivant ...une fois que tous le pi on criblés , fin et résultat...ce qui limitera les opérations des derniers indices qui seront inutiles...
de ton exemple:
(37, 53) (37, 47) (37, 43) (37, 41) (37, 37)
(41, 53) (41, 47) (41, 43) (41, 41)
(43, 53) (43, 47) (43, 43)
(47, 53) (47, 47)
(53, 53)
Pour info : dans l'algorithme nbpremier le groupe multipl GM fait constamment des break...pour faire partir les pi premiers qui ont été extraits par le GM...
#446 Re : Programmation » crible en python » 19-12-2018 20:52:21
oui effectivement avec la bonne version tu dois avoir pour n 300 000 000 fam 7;
>Calcul du tableau terminé!
>Le dernier nombre est:
299999977
>trouvé à la position:
2031596
donc avec nbpremier c'est moins d'une seconde, aà titre d'info, tel qu'il est pour 3 000 000 000 il met le même temps que nbpremier win..8100 seconde pour n = 450 000 000 000....mais c'est normal il fait trop d'opération
8000 seconde c'est le temps que met cribleG4Y ,ta dernière version #.V.6.3# ; pour n = 30 000 000 000.
la version python ...>C++ ; met 7 secondes pour 129 000 000 000.
-
#447 Re : Programmation » crible en python » 19-12-2018 15:50:53
Est ce que tu peux donc bloquer l'opération à l'index ok ..mais pour a*b %30 == 7..ou autre fam ??
cela ne ferait que 39 au lieu de 78 multiplications ...pour n = 3000. c'est toujours 3 fois plus que Goldbach pour le calcul des reste
Mais si on peut les faire partir à l'index commun aux deux pi...Alors c'est génial...! il ne resterait que 16 multipli...
ton tableau i = 0
(7, 7) (7, 11) (7, 13) (7, 17) (7, 19) (7, 23) (7, 29) (7, 31)
i = 1
(11, 11) (11, 13) (11, 17)
i = 2
(13, 13) (13, 17) (13, 19)
i = 3
(17, 17) (17, 19) (17, 23) (17, 29) (17, 31) (17, 37) (17, 41)
i = 4
(19, 19) (19, 23) (19, 29) (19, 31) (19, 37) (19, 41) (19, 43
i = 5
(23, 23) (23, 29)
i = 6
(29, 29) (29, 31) (29, 37) (29, 41) (29, 43) (29, 47) (29, 53)
i = 7
(31, 31) (31, 37)
i = 8
la c'est fini si/si tous les pi ont criblés !!! ; car à partir de cette limite > 31 on ne peut plus faire partir les pi {37..à.. 53} si il ne sont aussi partis à l'index commun aux deux pi quand c'est le cas en général..
(37, 37) (37, 41) (37, 43) (37, 47) (37, 53) fin pour 37 car son conjoint est 61 > 53 ; mais de plus il a déjà criblé
i = 9
(41, 41) (41, 43) (41, 47)
i = 10
que l'on ne traite pas , car b = 43 a déjà criblé
i = 11
(47, 47) (47, 53) dernière boucle pour l'index = 86 , par pas de 47 et de 53 donc ils sortent directement seul la cellule [47*53] serra transformer en [0]
Donc 44 opération au total pour les 13 premiers = a.
#448 Re : Programmation » crible en python » 19-12-2018 14:41:18
On ne s'est pas compris,...tu as étais clair...
j'étais en train de répondre et je n'ai pas enlevé ma question.
pour ceci ok
1. Le 1er crible est celui obtenu si j'oblige la boucle for b à s'arrêter puis à cribler après avoir trouvé le 1er b tel que 11*b%30 =7 donc un index de 11*17//30, donc 6...
Pour celui ci ça ne sert à rien et tu l'as bien compris..!
2. Le crible2 est celui qu'on obtient en laissant la boucle for b à aller jusqu'au bout (b=53) et donc qui traite l'index 47*11//30=17
Je constate alors que le crible n°1 et le crible n°2 diffèrent par le 0 ou le 1 à l'indice 6.
puisque dans ce cas cela fausserait le crible, il partirait d'un index 17 au lieu de 6 et par conséquent on aurait un nombre 1 comptabilisé en plus...!
les résultats faux que j'avais indiqués c'est le Gcrible ...terminé avec lui; j'ai repris ta version que j'ai reposté au # post 315, page 13...il n'y a plus d'erreur..
et pour n 300 000 000 E_cribleG3Y :
Extraction des premiers 7 à n : 0.09360003471374512 seconds ---
** 2031596 nombres trouvés en 207.9795651435852 secondes ** au lieu de ...
Extraction des premiers n à 2*n : 0.07800030708312988 seconds ---
** 1884105 nombres trouvés en 1.3260021209716797 secondes **
>>>
#449 Re : Programmation » crible en python » 19-12-2018 13:52:55
re Tu as bien fait ...!
A)
tu n'as pas de calcul redondant , c'est exact, mais le nombre d'opérations est très important par rapport à Goldbach qui inférieur :, c'est pourquoi ensuite il faut optimiser comme je l'ai indiqué sur le dernier post.
B) crible 1 ok pour 11²
le 2 ; crible avec 11 il est bon puisque en partant de l'indice 6 , tu marque un 0 tous les 11 nombres mais l'indice 6 c'est aussi pour 17 ...et les 0 par pas de 17 ....???
j'ai mis ton programme version ##6.2## au post 315 page 13 en remplacement du Gcrible car il me gonfle et je lui ai apporté tes modif ..pour l'instant afin de vérifier si pour la fam 1 il fonctionne ...ET ...il marche ..Mais en gardant dans la def eratostene sqrt 2n...? ce qui n'est pas normal...
.je te met le résultat pour n = 3000 sqrt < 54 ok
== RESTART: E:\Documents\Conjecture de Goldbach\CRIBLE_Eratosthène_Mod30.py ==
Donnez la valeur de n = 30k : 3000
Phase d'initialisation: 0.0 seconds ---
Bloc S2_s3 : 0.0 seconds ---
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1]
Extraction des premiers n à 2*n : 0.0 seconds ---
** 51 nombres trouvés en 0.0 secondes ** à ce résultat , il faut enlever 1 , donc 50
>>>
j'ai testé jusqu'à 30 00 000 000 résultat ok .
par contre le temps mis, 10 fois moins vite que Goldbach G3Y ce qui s'explique par le nombres d'opé...
regarde le post 315 pour charger le programme et y apporter ton savoir...ce qui va te permettre de voir les lignes que j'ai remplacées...
pour les opération de multiplication on est ok ..mais suppose maintenant qu'il faut que tu les arrêtes lorsque le produit par exemple :
fam 7 ; n 3000 est = à 7%30 donc il faut les faire partir pour cribler...
donc :
(11, 11) (11, 13) (11, 17) (11, 19) (11, 23) (11, 29) (11, 31) (11, 37) (11, 41) (11, 43) (11, 47) (11, 53)
i = 2
la partie rouge ne doit pas être effectué...ok?
D) je met le criblage pour la fam 7 et n = 3000
== RESTART: E:\Documents\Conjecture de Goldbach\CRIBLE_Eratosthène_Mod30.py ==
Donnez la valeur de n = 30k : 3000
Phase d'initialisation: 0.0 seconds ---
Bloc S2_s3 : 0.0 seconds ---
[1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0]
Extraction des premiers n à 2*n : 0.0 seconds ---
** 55 nombres trouvés en 0.0 secondes **
pour n = 30 000 ; fam = 7
nbpremiers win32 Eratosthènemod30
Allocation du Tableau en cours...
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
29947
>trouvé à la position:
407
ta version #v.6.2# mais pour pour Eratosthène:
== RESTART: E:\Documents\Conjecture de Goldbach\CRIBLE_Eratosthène_Mod30.py ==
Donnez la valeur de n = 30k : 30000
Phase d'initialisation: 0.0 seconds ---
Bloc S2_s3 : 0.0 seconds ---
Extraction des premiers n à 2*n : 0.0 seconds ---
** 407 nombres trouvés en 0.0 secondes **
>>>
Maintenant reste à y apporter ta TOUCHE ....
dans cette partie du programme :
for i,pi in enumerate(Primes_init):
for b in (Primes_init)[i:]:
j = pi*b
if j%30 == 7: # changer le paramètre pour une fam fxée
fam = P8[7] # changer le paramètre pour une fam fxée
debut_index = j//30
Nombres_fam = nombres[fam]
for index in range(debut_index, nbcell,pi):
Nombres_fam[index] = 0
afin déjà , qu'il aille aussi vite que Goldbach ta version #V.6.3# ou 2 peu importe..
**********************************************************************
aperçu entre les deux cribles version Gold et version Erat
===== RESTART: E:\Documents\Conjecture de Goldbach\cribleG3Y_modulo30.py =====
Donnez la valeur de n = 30k : 30000000
Extraction des premiers n à 2*n : 0.04679989814758301 seconds ---
** 213125 nombres trouvés en 0.15600013732910156 secondes **
>>>
== RESTART: E:\Documents\Conjecture de Goldbach\CRIBLE_Eratosthène_Mod30.py ==
Donnez la valeur de n = 30k : 30000000
Phase d'initialisation: 0.015599966049194336 seconds ---
Bloc S2_s3 : 5.85001015663147 seconds ---
Extraction des premiers 7 à n : 0.0 seconds ---
** 232262 nombres trouvés en 5.865610122680664 secondes **
>>>
@+
>>>
#450 Re : Programmation » crible en python » 18-12-2018 08:29:55
Suite du post ci-dessus:
Je suppose que la fonction range ne changerait rien à la place de enumérate, dans le but d'appeler les pi d'eratosne(n) afin d'utiliser les indices ['i] pour calculer les produit :
j = a * b
de sorte que lorsqu'un j a été calculé et qu'il est égal à j%30 == fam, puis on a calculé son index : soit pour a ou pour a et b suivant j est le carré de a.
Donc : a et b sont deux (premiers(n)) eratostene appelé, ils vont donc aller cribler....> n/30.
alors pourquoi ne pas mettre à 0 ces deux indices ['i] pour ne pas les rappeler...?
De sorte, que l'indice: i +1 du [premier] suivant, si i +=1 est marqué 0 , on saute et on utilise l'indice suivant:
i += 1, +=1, pour tout indice > 0.....non ?
En exemple:
=
{7, 11 13 17 19 23 29 31 37 41 43 47 53} indice i +=1:
{0, 1 , 2 , 3, 4 ,5 , 6 , 7, 8 , 9, 10,11, 12}
ce qui donnerait pour calculer j:
i*i , i * i+1, i *j+2 qui %30 = fam
index de j //30 = 3 index de a et b,
a crible , puis b crible, on met leur deux indices à 0 ce qui donne
{0, 1 , 0 , 3, 4 ,5 , 6 , 7, 8 , 9, 10,11, 12} on réitère avec l'indice suivant qui est 1.
i*i qui %30 = fam
index de j //30 = 4 index de a , qui crible...>n/30 , on met son indices à 0 ce qui donne :
{0, 0 , 0 , 3, 4 ,5 , 6 , 7, 8 , 9, 10,11, 12}; on réitère avec l'indice i +=1 suivant qui est 0 ; donc i += 1 indice 3
i*i , i* i +1 , i * i+2 qui %30 = fam
index de j //30 = 13 .. index de aet b, , qui criblent...>n/30 , on met leurs indices à 0 ce qui donne :
{0, 0 , 0 , 0, 4 ,0 , 6 , 7, 8 , 9, 10,11, 12} ..etc on réitère...avec i = 4 qui serra un carré congru à 1 (mod30)
Pourquoi on peut supprimer les pi qui ont criblé , ou mettre leurs indices à 0 ...?
Tout simplement , pour fam = 1 fixée:
pi = 7 , va parcourir les pi de Fam =13 , inversement 13 va parcourir les pi de Fam = 7:
Lorsqu'ils criblent ils marquent leur "conjoints" C...d'où on peut partir du carré de pi ou plus loin...pour ne pas revenir en arrière...Et donc , ne pas refaire des multiplications et index inutile...pour 3000: 18 au lieu de 72 ou 169...
Ex : je prend pi = 43 je fais i,a *b = 43*7 et index ...Alors que 7 en criblant a marqué d'un 0 sa cellule. ainsi que 37...d'où l'indice de 43 a été mis à 0 part 37, et l'indice de 53 mis à 0 par 17...lis ne peuvent donc pas être utilisé ensuite car ils ont déjà criblés...!
("Ce qui n'est pas faisable avec le Gcrible de Goldbach...car on part de l'indice du reste Ri.")
7 *13 ; 7*43; 7*73 ; 7* C+30 .....7 *C+30k
13 *37 , 13*67, 13 *97 ; 13 * C +30 .....13*C+30k....
11 *11 , va parcourir sa Fam = 11 +30k
17*23 vont parcourir fam 23+30k et 17+30k
19*19 ,va parcourir sa Fam = 19 +30k
29*29 ,va parcourir sa Fam = 29 +30k et en dernier :
31*31 ,va parcourir sa Fam = 31 +30k qui est la fam 1+30k
c'est un résumé du GM (groupe multiplicatif)de l'algorithme nbpremier en c++ Mais qui par cette méthode serra optimiser au maximum...pour fam = 1 ou 19 ,il y a 6 couples de base car il y a les carrés de pi, et pour les autres 4 couples.
pour fam =7 , on aura : 7 *31 ..c+30k et inversement , 11* 17 ...c+30k ; 13 *19 ..c+30, et 23 *29 ..c+30k
etc..
Ce qui en principe pour chaque indice i traité et par Pfam i, avec pi i, on doit limiter le nombre d'opération à 8 au maximum en fonction de chaque Pfam appelée par la fonction range; afin de calculer l'index de a*b ou de a*a...!pour ensuite cribler par pas de a de l'index à n//30.