Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#626 Re : Programmation » crible en python » 20-03-2018 17:36:16
Alors ...bien évidemment, certain programme donne une erreur lorsque l'on prend une petite limite ; par exemple l'algorithme Win nbpremier ne fonctionne qu à partir de 15000 / 30..si tu donnes n = 30 il va te donner une ligne de 1 qui sont les premiers 1 ; 7 11 13 17 19 23 et 29 et donc < 30. Sachant que 1 n'est pas premier, il n'y a rien à cribler.... d'autant que tu n'as que 7 qui est < à racine carrée de 60. Tu auras donc toujours un décalage d'une ligne avec l'algorithme: crible_mod30 . Alors que l'algorithme : crible_G(n) te donneras bien 7 nombres premiers de 30 à 60.
Probablement que le tableau des 8 Familles fait dans crible_mod30 par mon petit fils comporte une anomalie en programme Python..du fait que la première ligne N°0, de [1] est < 30. donc pour n= 60 je prends 30k + 30...soit N = 90 qui me donne trois lignes dans le tableau
Mais ça n'a aucune importance, car prend les 3 cribles : Eratosthène , crible_G(n) et crible_mod30 , donne N =1530 et même Win nbpremier tu auras bien 196 premiers de 1530 à 3060. De plus si tu cribles manuellement tu verras qu'il y a aucune erreur... et pour cause c'est le principe Eratosthène dans les congruences ...qui est très simple.
si manuellement je prend N = 30 donc Pi < sqrt 60 = 7 ; le reste R de 60 par Pi = 4 ; N /30 = 1 ; soit la ligne N°0
initialisation du tableau :
{familles........1....7.....11...13....17....19....23....29 }
Ligne N° 0 : [1] . [1] . [0] . [1] . [1] . [1] . [1] . [1]
criblage des 8 familles:
4 +7 = 11 donc le troisième [1] =11 est remplacé par [0] on continue 11+ (2*7) = 25 ; 25 +(2*7) > N = 30 fin du crible.
Extraction des nombres premiers, tu as donc bien 7 nombres premiers q de 30 à 60, car seul 11 est marqué [0] donc, congrus 60 (mod 7) , qui donne : 60 -11 = 49 = 7² c'est tout..
Mais effectivement , le programme aurait dû compter les sept [1] de la ligne N°0 ; qui correspondent bien à l'extraction des sept premiers de 30 à 60.... Même en ne donnant qu'une petite valeur pour N = 30.
Je ne peut pas te dire comment mon petit fils à simplifié le programme ou si il a omis des instructions...Ou est ce que pour des petites valeur de N = 30k le tableau est mal fait ou encore l'extraction se fait mal...Je lui est bien dit pour extraire les nombres premiers de n à 2n tu comptes uniquement les cell [1]. Ce qui se fait très bien dans crible_G(n)... Est ce que lui il a voulu faire dans l'extraction des nombres premiers q : 2n - [1] ...? ce qui est inutile, puisque seul les cell [1] donnent les premiers q de n à 2n; d'où on extrait les [1]...
Voila ...
#627 Re : Programmation » crible en python » 16-03-2018 15:43:26
Bonjour
@Yoshi : c'est quoi la variable Pï...? tu veux parler des nombres premiers [tex] P_i[/tex]...? et des restes [tex] R_i[/tex] de la division Euclidienne de [tex]\frac{30k}{P_i} = R_i[/tex]....
Les familles, son 8 suites en progression arithmétique de raison 30 et de premiers termes 1 ou P premier appartenant à [tex][7 ; 29][/tex]
A+ ..Merci...
#628 Re : Programmation » crible en python » 15-03-2018 10:29:20
Bonjour
j'en suis toujours au même point. je n'ai pas réussi à modifier le programme ci-dessous pour qu'il ne travaille "crible" que dans une seule famille...
j'ai remplacé 8 par 1 dans cette ligne: nombres = [[1 for _ in range(nbcell)] for _ in range(8)] pour n'avoir qu'une colonne de [1] ou ligne de [1]
j'ai remplacé cette ligne : p8 = [1, 7, 11, 13, 17, 19, 23, 29] par, p8 = 1 pour ne travailler que dans la famille 1 modulo 30
la ligne en dessous pfam = [] , je n'y ai pas touché mais je ne sais pas quel est son rôle...?
j'ai mis un # devant les lignes : #elif d_c == '3': # on vérifie 13 et 23 ; #elif d_c == '7': # on vérifie 7 e17 ,et, #else: # on vérifie 19 et 29 (d_c = 9) afin qu'elle ne soient pas pris en compte dans le programme
je suppose que cette ligne: pfam.append([0, 0, 0, 0, 0, 0, 0, 0]) pose problème si je travaille que dans une colonne [1]...?
et ensuite j'ai remplacé le (8) par (1) dans les lignes for j in range(8)
sans résultat....?
voici la partie du programme à modifier à partir de la ligne 102 dans pycharme:
# ATTENTION: n doit être multiple de 30
def crible_mod30(n):
# INITIALISATION
start_time = time.time()
nbcell = int(n/30)
nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
p = eratostene(int(n))
p = p[3:]
lenp = len(p)
r = []
p8 = [1, 7, 11, 13, 17, 19, 23, 29]
pfam = []
print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))
# FAMILLES POUR CHAQUE Pi
start_time = time.time()
for i in range(lenp):
r.append(2*n % p[i])
pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
j = r[i]
incr = p[i]*2
d_c = str(j)[-1]
# On elimine les restes pairs
if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
j += p[i]
d_c = str(j)[-1]
while j < n:
if d_c == '5' or j % 3 == 0: # on passe au suivant
fam = -1
elif d_c == '1': # on vérifie 1 et 11
if j % 30 == p8[0]:
fam = 0
else:
fam = 2
elif d_c == '3': # on vérifie 13 et 23
if j % 30 == p8[3]:
fam = 3
else:
fam = 6
elif d_c == '7': # on vérifie 7 et 17
if j % 30 == p8[1]:
fam = 1
else:
fam = 4
else: # on vérifie 19 et 29 (d_c = 9)
if j % 30 == p8[5]:
fam = 5
else:
fam = 7
if fam != -1 and pfam[i][fam] == 0:
pfam[i][fam] = j
j += incr
d_c = str(j)[-1]
print("Crible mod30 : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))
# ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE Pi
start_time = time.time()
lenpfam = len(pfam)
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]
print("Crible mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))
# AFFICHAGE
for i in range(8):
count = 0
for cell in nombres[i]:
if cell == 1:
count += 1
# CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
start_time = time.time()
premiers = []
for i in range(8):
for j in range(nbcell-1, -1, -1):
if nombres[i][j] == 1:
premiers.append(nombres[i][j] == 1)
print("Crible mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
premiers.sort()
return premiers
n = int(input("Donnez la valeur de N = 30k : "))
#nb = len(crible_G(n))
#print("On a "+str(nb)+" nombres premiers")
#print("---------------------------------------------------------")
nb = len(crible_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
je remet si-dessous l'intégralité du programme qui fonctionne bien dans les 8 Familles modulo 30 : Si quelqu'un peut me dire ce que je dois modifier, pour que le crible fonctionne que dans une Famille par exemple la famille p8 = 1 , Ca serait sympa....Dans l'attente Merci...
import math
import time
def eratostene(n):
n = int((2*n)**0.5)
m = (n-1) // 2
b = [True]*m
i = 0
p = 3
premiers = [2]
while p*p < n:
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i += 1
p += 2
while i < m:
if b[i]:
premiers.append(p)
i += 1
p += 2
return premiers
#def compteInfN(liste, n):
compte = 0
lenListe = len(liste)
for i in range(0, lenListe):
if (liste[i] >= n):
compte += 1
return compte
#def premiersNa2N(n):
#liste1 = eratostene(n)
liste2 = crible_G(n)
print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
#print("> N / log(2N) = " + str(n / math.log(2 * n)))
#print("> Pi(2N) = " + str(len(liste1)+len(liste2)))
print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
print("> Estimation Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
#print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
# print(liste2)
#def crible_G(n):
# INITIALISATION
start_time = time.time()
nombres = n*[1]
nombres[0] = 0
p = eratostene(int(n))
lenp = len(p)
r = []
print("Crible G: Initialisation: %s seconds ---" % (time.time() - start_time))
# CRIBLAGE DES NOMBRES
start_time = time.time()
for i in range(lenp):
r.append(2*n % p[i])
j = r[i]
while j <= n:
nombres[j-1] = 0
j += p[i]
print("Crible G: Criblage des entiers 1 à n: %s seconds ---" % (time.time() - start_time))
# EXTRACTION DES_NOMBRES_PREMIERS
start_time = time.time()
premiers = []
for i in range(n-1, 0, -1):
if nombres[i] == 1:
premiers.append(nombres[i] == 1)
# on regarde si il y a un reste égal à 1
resteUn = 0
lenr = len(r)
for i in range(lenr):
if r[i] == 1:
resteUn = 1
# si aucun reste n'est égal à 1 2*n-1 est premier
if resteUn == 0:
premiers.append(2*n-1)
print("Crible G: Extraction premiers n à 2*n: %s seconds ---" % (time.time() - start_time))
return premiers
#def fam_reste(reste, p8):
i = 0
while i < 8 and reste % 30 != p8[i]:
i += 1
if i == 8:
return -1
else:
return i
# On travaille avec 8 familles (1, 7, 11, 13, 17, 19, 23, 29)
# ATTENTION: n doit être multiple de 30
def crible_mod30(n):
# INITIALISATION
start_time = time.time()
nbcell = int(n/30)
nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
p = eratostene(int(n))
p = p[3:]
lenp = len(p)
r = []
p8 = [1, 7, 11, 13, 17, 19, 23, 29]
pfam = []
print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))
# FAMILLES POUR CHAQUE Pi
start_time = time.time()
for i in range(lenp):
r.append(2*n % p[i])
pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
j = r[i]
incr = p[i]*2
d_c = str(j)[-1]
# On elimine les restes pairs
if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
j += p[i]
d_c = str(j)[-1]
while j < n:
if d_c == '5' or j % 3 == 0: # on passe au suivant
fam = -1
elif d_c == '1': # on vérifie 1 et 11
if j % 30 == p8[0]:
fam = 0
else:
fam = 2
elif d_c == '3': # on vérifie 13 et 23
if j % 30 == p8[3]:
fam = 3
else:
fam = 6
elif d_c == '7': # on vérifie 7 et 17
if j % 30 == p8[1]:
fam = 1
else:
fam = 4
else: # on vérifie 19 et 29 (d_c = 9)
if j % 30 == p8[5]:
fam = 5
else:
fam = 7
if fam != -1 and pfam[i][fam] == 0:
pfam[i][fam] = j
j += incr
d_c = str(j)[-1]
print("Crible mod30 : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))
# ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE Pi
start_time = time.time()
lenpfam = len(pfam)
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]
print("Crible mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))
# AFFICHAGE
for i in range(8):
count = 0
for cell in nombres[i]:
if cell == 1:
count += 1
# CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
start_time = time.time()
premiers = []
for i in range(8):
for j in range(nbcell-1, -1, -1):
if nombres[i][j] == 1:
premiers.append(nombres[i][j] == 1)
print("Crible mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
premiers.sort()
return premiers
n = int(input("Donnez la valeur de N = 30k : "))
#nb = len(crible_G(n))
#print("On a "+str(nb)+" nombres premiers")
#print("---------------------------------------------------------")
nb = len(crible_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
#629 Re : Programmation » crible en python » 02-02-2018 11:57:42
Bonjour
@Yoshi :
Pour info voici le lien du fichier qui donne les explication de cet algorithme crible_mod30; que mon petit fils va modifier ce Week-end , pour cribler par famille.
j'ai déjà modifier afin de simplifier le criblage-mod30 , dont le programme python actuel est en fin de document (il n'y a eut en définitive, que deux lignes à modifier suivant tes instructions...la ligne de def eratostene (2*n**.05)) et la dernière,
n = int(input("donner la valeur N +30 : "))
de ce fait il prend la valeur n = 30k jusqu'à 4 500 000 000, au lieu de 975 000 000 ....ce qui permet de voire l'évolution de la répartition des nombres premiers [n ; 2n]; par tranche de 30 000 000. et de vérifier le rapport (n / 3,75) / Pn qui est le nombre de premiers de n à 2n.etc ...etc
Bonne journée.
#630 Re : Programmation » crible en python » 30-01-2018 06:50:20
re, Je comprend parfaitement Yoshi, d'autant que je vais envoyer à mon petit fils, la modif que tu m'as apporté, et avec ce fichier qu'il me modifie les lignes relatives à crible_mod30; si .... il n'est pas trop pris par sa préparation et sa remonté des notes, afin qu'il puisse être admis à son concourt sur Montréal ....je t'ai envoyé le fichier pour info....et je te remercie encore, bon courage en attendant....
A+ LEG
#631 Re : Programmation » crible en python » 29-01-2018 17:48:44
Bonjour :
@Yoshi est ce que ce fichier , pour le programme cible_mod30 est plus facile à comprendre , c'est ce que mon petit fils aurait dû programmer par Famille, et non les 8 Familles d'un coup. Ce qui je pense aurait été plus simple, et plus facile...Tout comme il fallait faire appel à Eratosthène , mais jusqu'à racine carrée de 2n...ça encore avec la modification que tu m'as indiquée cela résout ce problème ..
donc voici le lien de ce petit fichier word...
bonne lecture.A+
#632 Re : Programmation » crible en python » 28-01-2018 16:08:14
Bonjour
@Yoshi voila ce que cela donne en temps par tranche de 30 000 000, ou en augmentant n de 1 000 000
comme tu le verras, j'ai bloqué la fonction crible_G(n) en mettant # devant les lignes de fonction dont je n'ai pas l'utilité....
Ce qui permet de cribler un peu plus loin et de diviser le temps par 2...
Mais je ne sais pas si c'est Python ou la mémoire dos, car je ne peux pas cribler n = 38 000 000 ; 1 140 000 000 .
Avec l'algo Nb premier je crible n= 15 000 000 000 de cellules = 1; soit jusqu'à 450 000 000 000; "mais par famille" et en C++.
Or, si on regarde, cela ne fait pour crible_mod30 que 38 000 000 * 8 = 304 000 000 de cellules = 1 .
Cela me suffit....
Le but étant toujours de cribler de 7 à 30*n, pour obtenir le nombre de nombres premiers de n à 2n et vérifier la fonction [tex]\frac{N}{Ln 2N}[/tex] relatif à G(n) .... tel que : 30(n+1) / Ln 60(n+1) vaut environ 2*(30n / Ln 60(n) - 30(n-1) / Ln 60(n-1)
A+
#633 Re : Programmation » crible en python » 27-01-2018 21:23:16
Re,
C'est toi le mieux placé pour voir ce qui va, ce qui ne va pas.
Je regarderai ça de plus près plus tard...
Je t'avais écrit :Et là, c'est maintenant crible_mod (qui "semble" bien plus touffu que le crible_G de départ...
il est pareil qu crible_G, si ce n'est que l'on a supprimé les 2n , 3n et 5n, il est un peu plus chia....à programmer..
le crible_G lui crible de 1 à n = n*30 , les entiers sont représentés aussi par des 1, donc pour n= 500 il y en a 15000 au lieu de 4000,
dans cribl_mod, car : 15000 /3,75 = 4000; ou si tu préfères pour n = 500; 500 * 8 = 4000 entiers congrus à 1 ou p [30] on a éliminé 73,333...% des entiers naturels > 0....etc
et dans crible_G, on par du reste R quelque soit sa forme pair ou impair et on rajoute P_i , biens sûr si R = 0 et bien tu pars de P_i mais le principe et le même que crible Eratosthène...C'est pour cela que ce crible, prouve que le nombre de premiers [n ; 2n] est obligatoirement
< à pi(n) ... même si il n'y avait pas de nombres premiers entre [tex]\sqrt{n}[/tex] et [tex]\sqrt{2n}[/tex]....c'est facile à prouver....
il en ressortira que G(n) fonction qui compte les entiers [tex]\not\equiv{2n}[P_i][/tex] l, c'est à dire les nombres premiers q appartenant à [n ; 2n]....
Au fait, c'est cela que tu as implémenté : www.bibmath.net/forums/viewtopic.php?id=9001&p=3 (dernier post) ?
@+
Non pas du tout, de toutes façons, les entiers dans le tableau des 8 familles relatif au crible_mod ils sont représenté par 8 colonne de 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
...etc ...
jusqu'à lim n , si n= 500 cela donne 500 lignes de 8 colonne et tu auras criblé de 1 à 15000 par colonne , mais le premier 1 est criblé, si et seulement si, dans les restes R de n*30 par P_i si il existe un R = 1 alors le premier 1 se transforme en 0 et donc 2n-1 = n'est pas un nombre premier, et inversement si il n'y a pas de R = 1 ("exit les 2m,3m et 5m" bien entendu).
Par exemple dans la première colonne d'entiers [tex]\equiv{1}[30][/tex] le premier 1 est marqué 0, le deuxième 1 = 31 est aussi marqué 0 donc 30000 -1 n'est pas premier, ni 30000 - 31.
la première ligne de 1, représente:
1.7.11.13.17.19.23.29
et ensuite tu rajoutes 30 dans chaque colonne jusqu'à n
("donc la première ligne est < 30 ; c'est pour cela qu'il y a un décalage lorsque l'on crible, je rajoute toujours 1 à n") afin de cribler,
30000 -1 car dans le programme en principe si R = 1, alors 2n -1 n'est pas premier or lorsque l'on indique n = 500, en réalité on a 499*30 -1 = 14969 , puisque la première ligne ne peut valoir ou être > 30, alors que si je prend n+1 donc = 501, et (501 - 1)*30 - 1= 14999.
et on part du reste R si et seulement si il est congru à 1 ou P modulo 30 afin de le placer dans sa famille et si R = 0 donc la on part de P_i relatif à sa famille et on calcul les 7 autres entiers, tel que R + P_i congru à 1 ou P modulo 30....
c'est ce qui est écrit dans le programme....
je suis mûr pour les cribles mais surement pas pour Python....Lollll. je n'aime pas la langue anglaise de plus je programmerai rien d'autre avant des lustres....en principe....C'est le seul crible qu'il me fallait faire programmer....
Mais Merci de m'avoir poussé à chercher , à regarder : programmer en Python, pour essayer de comprendre ce que mon petit fils à fait ...etc, et surtout ton dévouement..
Bonne soirée Yoshi et pour une bonne bouteille ou repas cela tient toujours.....
A+
#634 Re : Programmation » crible en python » 27-01-2018 17:24:14
Re,
n = int(input("Donnez la valeur de N : "))
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(30*n))
print("On a "+str(nb)+" nombres premiers")
input()
@+
attention ça cela ne marche pas il se produit un double criblage de cribl_G
il me faut bien écrire comme je l'ai fait dans le programme joins :
n = int(input("Donnez la valeur de N : "))
n = 30*n
nb = len(crible_G(n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_mod(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
#635 Re : Programmation » crible en python » 27-01-2018 17:05:31
Re,
Oui.
n = int(input("Donnez la valeur de N : "))
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
ok, mais si je fais cela alors il effectue deux fois le criblage du crible _G .. mais comme je ne l'ai pas écrit exactement pareil, et que cela marche comme je l'ai écrit dans le dernier post dernier paragraphe ...j'attends qu'il finisse 30*n=1 020 000 000 si cela passe car avec l'ancienne version il tourne il tourne le furet......
Modif cosmétique suggérée
Au début du programme, tu peux ajouter :
import os
et remplacer le input() final par
os.system("pause")
Ça ne change rien, sinon que c'est plus "propre"...
@+
ça ensuite je l'essaye.
pour en revenir à ta question, pour le crible_G2 appelé maintenant crible_mod
c'est le même mais comme je l'ai expliqué un peu vite...lui il crible les entiers n congrus à1 ou P (mod Pi) avec P premier appartenant à [7 ; 29], sachant que 1 n'est pas premier donc dans le crible il est remplacé par 31...etc
voila pourquoi dans ce crible on fait un tableau de 8 Familles " suite en progression arithmétique de raison 30 et de premier terme :
{1.7.11.13.17.19.23 et 29}
ce qui permet de cribler par famille : modulo (P_i *30) une fois que les restes R ou P_i lorsque R = 0, sont positionnés au départ dans chaque Famille...
cela gagne du temps et de la place en mémoire...bien sur en supprimant dans crible_mod , la fonction : def crible_G(n)
mais cela je ne l'ai pas fait pour l'instant , car je risque de me planter dans la suppression des lignes relatif à crible_G(n)...sans altérer le fonctionnement crible_mod peut être simplement en mettant # devant def crible_G(n) et en supprimant les trois dernières lignes
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
et je garde uniquement ce que tu as écrit en bleu...
je te joins la copie crible_mod ci dessous ce qui va te permettre de mieux comprendre...si besoin est ...
import os
import math
import time
def eratostene(n):
n = int(n)
m = (n-1) // 2
b = [True]*m
i = 0
p = 3
premiers = [2]
while p*p < n:
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i += 1
p += 2
while i < m:
if b[i]:
premiers.append(p)
i += 1
p += 2
return premiers
def compteInfN(liste, n):
compte = 0
lenListe = len(liste)
for i in range(0, lenListe):
if (liste[i] >= n):
compte += 1
return compte
def premiersNa2N(n):
#liste1 = eratostene(n)
liste2 = crible_G(30*n)
print("> On prend N = " + str(30*n) + " , donc 2N = " + str(2 * 30*n))
#print("> N / log(2N) = " + str(n / math.log(2 * n)))
#print("> Pi(2N) = " + str(len(liste1)+len(liste2)))
print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
print("> Estimation Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(30*n) + " et " + str(2 * 30*n))
#print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
# print(liste2)
def crible_G(n):
# INITIALISATION
start_time = time.time()
nombres = n*[1]
nombres[0] = 0
p = eratostene(int((2*n)**0.5))
lenp = len(p)
r = []
print("Crible G: Initialisation: %s seconds ---" % (time.time() - start_time))
# CRIBLAGE DES NOMBRES
start_time = time.time()
for i in range(lenp):
r.append(2*n % p[i])
j = r[i]
while j <= n:
nombres[j-1] = 0
j += p[i]
print("Crible G: Criblage des entiers 1 à n: %s seconds ---" % (time.time() - start_time))
# EXTRACTION DES_NOMBRES_PREMIERS
start_time = time.time()
premiers = []
for i in range(n-1, 0, -1):
if nombres[i] == 1:
premiers.append(2*n-i-1)
# on regarde si il y a un reste égal à 1
resteUn = 0
lenr = len(r)
for i in range(lenr):
if r[i] == 1:
resteUn = 1
# si aucun reste n'est égal à 1 2*n-1 est premier
if resteUn == 0:
premiers.append(2*n-1)
print("Crible G: Extraction premiers n à 2*n: %s seconds ---" % (time.time() - start_time))
return premiers
def fam_reste(reste, p8):
i = 0
while i < 8 and reste % 30 != p8[i]:
i += 1
if i == 8:
return -1
else:
return i
# On travaille avec 8 familles (1, 7, 11, 13, 17, 19, 23, 29)
# ATTENTION: n doit être multiple de 15
def crible_mod(n):
# INITIALISATION
start_time = time.time()
nbcell = int(n/30)
nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
p = eratostene(int((2*n)**0.5))
p = p[3:]
lenp = len(p)
r = []
p8 = [1, 7, 11, 13, 17, 19, 23, 29]
pfam = []
print("Crible mod : Initialisation: %s seconds ---" % (time.time() - start_time))
# FAMILLES POUR CHAQUE Pi
start_time = time.time()
for i in range(lenp):
r.append(2*n % p[i])
pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
j = r[i]
incr = p[i]*2
d_c = str(j)[-1]
# On elimine les restes pairs
if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
j += p[i]
d_c = str(j)[-1]
while j < n:
if d_c == '5' or j % 3 == 0: # on passe au suivant
fam = -1
elif d_c == '1': # on vérifie 1 et 11
if j % 30 == p8[0]:
fam = 0
else:
fam = 2
elif d_c == '3': # on vérifie 13 et 23
if j % 30 == p8[3]:
fam = 3
else:
fam = 6
elif d_c == '7': # on vérifie 7 et 17
if j % 30 == p8[1]:
fam = 1
else:
fam = 4
else: # on vérifie 19 et 29 (d_c = 9)
if j % 30 == p8[5]:
fam = 5
else:
fam = 7
if fam != -1 and pfam[i][fam] == 0:
pfam[i][fam] = j
j += incr
d_c = str(j)[-1]
print("Crible mod : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))
# ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE Pi
start_time = time.time()
lenpfam = len(pfam)
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]
print("Crible mod : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))
# AFFICHAGE
for i in range(8):
count = 0
for cell in nombres[i]:
if cell == 1:
count += 1
# CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
start_time = time.time()
premiers = []
for i in range(8):
for j in range(nbcell-1, -1, -1):
if nombres[i][j] == 1:
premier = 2*n-((j*30)+p8[i])
premiers.append(premier)
print("Crible mod : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
premiers.sort()
return premiers
n = int(input("Donnez la valeur de N : "))
n = 30*n
nb = len(crible_G(n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_mod(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
#636 Re : Programmation » crible en python » 27-01-2018 14:46:10
pour le crible mod 30
il me crible deux fois crible mod 30
n = int(input("Donnez la valeur de N : "))
crible_G2(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(30*n))
print("On a "+str(nb)+" nombres premiers")
input()
et si je renseigne la deuxième ligne "crible_G(30*n)"
n = int(input("Donnez la valeur de N : "))
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(30*n))
print("On a "+str(nb)+" nombres premiers")
input()
il effectue deux fois le crible_G......?
il y a une erreur dans cette ligne...
voila je viens de modifier comme ceci :
n = int(input("Donnez la valeur de N : "))
n = 30*n
nb = len(crible_G(n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_mod(n))
print("On a "+str(nb)+" nombres premiers")
input()
et impeccable ....je vais boire un coup à ta santé....un grand merci.....
@+
#637 Re : Programmation » crible en python » 27-01-2018 12:47:28
j'ai modifié les lignes car ce n'était pas les bonnes valeurs
liste2 = crible_G(30*n)
print("> On prend N = " + str(30*n) + " , donc 2N = " + str(2 * 30*n))
print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(30*n) + " et " + str(2 * 30*n))
il faut aussi savoir que la valeur n rentrée dans ce cas n=500 soit 30*500..
on ne crible que jusqu'à 15000 -30 c'est à dire n -1 en criblant n=501 on a bien 1494 premiers de 15000 à 30000 sachant que 2n-1, n'est pas criblé .
dans mon algo nBpremier , il m'en donne 1495...
Donc Yoshi ou je te paye un bon resto ou tu veux une bonne bouteille, pour ton dévouement avec un grand merci ......
il me reste crible_G mod 30 à modifier pour vérifier les temps mis...
#638 Re : Programmation » crible en python » 27-01-2018 12:07:51
voila ce que j'ai refait la première ligne, la troisième, et la fin comme tu l'as indiquée:
nombres = [1]*n
nombres[0] = 0
p = eratostene(int((2*n)**0.5))
lenp = len(p)
r = []
for i in range(lenp):
r.append(2*n % p[i])
j = r[i]
while j <= n:
nombres[j-1] = 0
j += p[i]
premiers = []
print("√2N = "+str(int(math.sqrt(2*n))))
for i in range(n-1, 0, -1):
if nombres[i] == 1:
premiers.append(n-i-1)
# on regarde si il y a un reste égal à 1
resteUn = 0
lenr = len(r)
for i in range(lenr):
if r[i] == 1:
resteUn = 1
# si aucun reste n'est égal à 1 2*n-1 est premier
if resteUn == 0:
premiers.append((2*n)-1)
return premiers
n = int(input("Entrer un entier n"),n)
crible_G(30*n)
premiersNa2N(n)
input()
la fenêtre dos , s'ouvre bien, je rentre la valeur de n : 500
puis entrer et la fenêtre se ferme ....donc ?????
je viens de refaire un essais
mais avec la ligne:
et le reste comme ci-dessus
ET CA MARCHE
résultat :sqrt de 2n = 173 , v2n = 31 ça je ne sais pas ce que cela veut dire..., et on compte 73 premiers entre n et 2n
pour l'instant je n'ai pas vérifié mais je pense que cela doi être bon
@+
je vais modifier crible_Gmod 30.
#639 Re : Programmation » crible en python » 27-01-2018 10:46:56
suite du post ci-dessus , si j'ai bien suivi ton exemple
crible_G(30*n)
en prenant n=500 pour crible_G(n) on a n=15000 , donc 2n=30000 pour eratostène on a n=173
voila ce que donnerait les lignes print, où j'ai mis un # devant les lignes qui ne servent plus, et en gardant bien tel quel :
def premiersNa2N(n)....: puisque la valeur de n vaut 30*n =15000, dans cette fonction def.....ou faut il modifier quelque chose...?
# liste1 = eratostene(n*2)
compte = compteInfN(liste1, n)
liste2 = crible_G(n)
print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
# print("> N / log(2N) = " + str(n / math.log(2 * n)))
#print("> Pi(2N) = " + str(len(liste1)))
print("> Estimation du TNP Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
print("> Estimation Pi(2N)-Pi(N) = N/log(2N) = " + str(n / math.log(2*n)))
#print("> Avec eratosthene: On compte " + str(len(liste1)-compte) + " nombres premiers entre 1 et " + str(n))
#print("> Avec eratosthene: On compte " + str(compte) + " nombres premiers entre "+str(n)+" et " + str(n*2))
print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
# print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
# print(liste2)
#640 Re : Programmation » crible en python » 27-01-2018 10:07:41
Boniour
@Yoshi, tu as parfaitement compris ce que je veux modifier dans ce programme crible_G. Excuse de ne pas avoir répondu hier soir...
Bonsoir,
Mais, techniquement, si j'ai compris, oui, c'est faisable
Tu veux envoyer 30k à Eratostene ?
No pb.
Tu choisis n, tel que n=30k
puis pour crible_G() tu utilises crible_G(n).
Dans crible G(n)
* tu écris p=eratostene(n)
* tu écris : nombres =[1]*(n*n//2)
Ok je comprend parfaitement cette partie, mais je ne savais pas l'écrire , j'avais mis le [1] après (n*n//2) dans nombres = ,
pour p= eratosthne(n) pas de problème
mais pour eratosthene je veux lui envoyer n=30k qui est la racine carrée de 2*30k, comme ça, je ne change rien dans la première partie def eratostene (n)
et je vais me servir de ce n pour le reste; Ton idée est peut être plus simple à écrire ....
exemple [tex]2n = 900[/tex] , donc [tex]n=E(\sqrt(900))= 30[/tex] ce qui ne changera rien ci-dessus p= e....; et nombres=[1]*....
Mais la partie, la limite n que va cribler eratostene serra bien [tex]n\leqslant\sqrt{2*30k}[/tex] et non pas ce qui se passe ,ie; jusqu'à 2n....ce qui alourdit et prend du temps inutilement...
Mais Quelle valeur fournis-tu ici :
premiersNa2N(n)
le n = 30k ?
Comme tu t'en doute : cela serra donc :premiersNa2N(n*n//2)
Il faut que tu saches que la variable n que utilises dans la fonction eratostene et la variable n que tu utilises dans la fonction crible_G sont des variables locales qui portent le même nom mais sont différentes et ne sont pas visibles à l'extérieur.
Ca je l'avais compris...mais il faut que je modifie les Lignes de def crible_G , partout où il y a le n qui est utilisé ; et je pense que je dois mal écrire les modifications.... puisque cela me met des erreurs que je ne comprend pas....
Je peux même faire :
Input ("Entrer un entier n"),n
crible_G(30*n)
avec
def crible_G(n):
nombres=[1]*(n**2//2)
p=eratostene(n)
Ca , serait très bien, mais il faut modifier toutes les variable qu'il y a dans def eratostene (n) jusqu'à def crible_G...y compris les lignes input.....; qui de toutes façons, dans les deux cas je vais modifier et en supprimer, celles relatives à eratosthene et je n'en garde que 2 ou 3 utilisant le logarithme de [tex]\pi(n)[/tex] et [tex]\pi(2n)[/tex] et voir [tex]\pi(2n)[/tex] - [tex]\pi(n)[/tex]
Supposons n=500 : à l'arrivée dans crible_G(n), le n vaudra 15000 mais seulement 500 à l'extérieur...
Et donc si je suis bien, 2n = 30000... ?
Et si tu ne veux pas n=15000 pour eratostene(n), c'est à l'appel que ça se passe...
Supposons que dans eratostene tu veuilles [tex]n=E(\sqrt(15000))[/tex],
et bien, depuis crible_G tu écris p=eratostene(int((2*n)**0.5))
Et tu laisses :
def eratostene(n):
Oui je comprends mais je veux :[tex]n=E(\sqrt(2*15000))[/tex] je suppose que ce que tu as écrit de puis crible_G : p=eratostene(int((2*n)**0.5)), correspond à racine carrée de 30000...? c'est ça....? car en dessous tu as bien calculer la rcine carrée de 30000 = 173 pour eratostene où n= 173
Mais dans ce cas: est ce que pour nombres j'écris : nombres=n*[1] car dans crible_G(n) , n vaut 15000 si j'ai bien suivi...?
Ce qui fait qu'à l'extérieur des fonctions n = 500
dans crible, n= 15000
dans eratostene, n=173...
Tu piges le principe ?
Oui , mais est ce qu'il y a d'autre ligne à modifier...? en exemple les questions que tu me poses, ci-dessous....
Et pour
premiersNa2N(n) que vaut le n ?
compte = compteInfN(liste1, n) que vaut le n ?
pour la première question: avec ton exemple de n=500; le n = 30*n =15000
pour la deuxième question: je la supprime ou je met un # devant la ligne; car cette liste ne sert plus à rien je n'ai pas besoin de savoir ou de calculer la liste d'eratostene.
par contre la liste 2 il me la faut pour savoir combien il y a de premier de 30*n à 2*30*n
#641 Re : Programmation » crible en python » 26-01-2018 06:02:19
Bonjour
Ave,
@+
Les deux fonctions peuvent parfaitement cohabiter dans le même programme.
Il aura le même fonctionnement que d'habitude.Après, ainsi que je te l'ai dit, ça ne changera en rien ni tes habitudes, ni le fonctionnement.
Mais c'est inutile, ta fonction ou la mienne renvoient la même liste, et la tienne est 3 x plus rapide
je pense avoir trouvé la solution à mon petit problème :
a) il me suffit de rentrer au départ input la valeur de [tex](n)\leqslant\sqrt{2n} [/tex] avec 2n = (30k)²
b) Est ce qu'il faut que j'utilise une deuxième variable de (n) pour crible_G; par exemple
def carre(n)
retourn n*n
Par exemple je veux utiliser pour le crible _G [tex]carre(n)/2[/tex], afin de cribler jusqu'à 30k² / 2 les entiers [tex]\equiv{(30k)^2}[P_i] [/tex]
Ce qui me donnera les nombres premiers entre [tex][N ; 2N][/tex]
c) Puis pour la deuxième fonction qui est le crible _G , il suffit d'utiliser la valeur (n) tel que: ((carre(n) / 2) sans faire appel à la deuxième variable ci-dessus en b) par exemple :
[def crible_G ((carre(n)) / 2): au lieu de def crible_G(n)
nombres = n*n*/2 *1[1] "au lieu de nombres = n*[1] " ou, nombres = carre(n)/2 *[1]
nombres[0] = 0
p = eratostene(n) au lieu de (math.sqrt(2*n))
lenp = len(p)
r = []
for i in range(lenp):
Ou bien il faudrait rentrer deux valeurs de (n) la première pour Eratosthène = 30k ;
la deuxième pour crible_G [tex](n) = (30k)^2 / 2[/tex] mais est ce faisable...?
#642 Re : Programmation » crible en python » 23-01-2018 13:41:41
Bonjour
@Yoshi : pourquoi au lieu de faire appel à Eratosthène , on ne rentre pas une base de données de nombres premier , par exemple [tex]\leqslant\sqrt{2000000000}[/tex] ce qui fait en gros 4400 nombres premiers [tex]P_i [/tex] que la fonction du crible_G va utiliser , en fonction de la valeur de n rentrée à la demande...? ce qui évite un criblage, puis stockage ....etc etc...
soit d'emblée dans le programme on inclue la base de données [tex]P_i [/tex] soit à la demande en fonction de n donc les [tex]P_i\leqslant\sqrt{2n}[/tex] ..... tout simplement....
#643 Re : Programmation » crible en python » 22-01-2018 18:36:19
c'est quand même beaucoup moins rapide que mon crible NB premier, qui lui pour crible de 1 à n et de 1 à 2n jusqu'à 1 000 000 000 il met 28 secondes alors que dans pycharm pour le crible_mod 30 , tu as vu le temps qu'il met jusqu'à 990 000 000 au dela il ne prend pas , je suppose que cela vient qu'il crible Eratosthène jusqu'à n ou 2n, puis le crible_g jusquà n et le crible_mod 30 les 8 familles jusqu'à n
Le but de ce crible G ( en référence à Goldbach) c'est un outil identique à Eratosthène, qui implique la fonction du TNP pour une Lim n fixée
[tex]\frac{n} {Ln n}[/tex] d'ou on peut prouver que la fonction G(n) relatif au crible G, vaut [tex]\frac{n}{Ln 2n}[/tex] lorsque la lim n tends vers + l'infini...
Ce qui est vrai pour [tex]\pi(n)[/tex] et son crible Eratosthène est vrai pour [tex]G(n)[/tex] et son crible G : qui est Eratosthène dans les congruences mais avec le même principe...etc....etc.
Cette deuxième fonction [tex]\frac{n}{Ln 2n}[/tex] n'est autre, qu'un corollaire du TNP, grâce à cet outil de crible... il est vrai que dans le crible G on utilise les premiers [tex]P_i\leqslant\sqrt{2n}[/tex] au lieu de [tex]P_i\leqslant\sqrt{n}[/tex] d'où la fonction 2 avec le (log n ) de 2n...
#644 Re : Programmation » crible en python » 22-01-2018 18:16:18
Ok Yoshi
donc pour l'instant, je laisse en l'état, en attendant que je puisse modifier la première partie
def eratosthène , afin qu'il ne crible que jusqu'à la racine carrée de n lorsque l'on rentre la valeur de n. pour la fonction du crible_g dans le programme...
il faut je suppose remplacer la première partie du programme
import math
def eratostene (n):
n = int(n)
m = (n-1) // 2
b = [True]*m
i = 0
p = 3
premiers = [2]
while p*p < n:
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i += 1
p += 2
while i < m:
if b[i]:
premiers.append(p)
i += 1
p += 2
return premiers
def compteInfN(liste, n):
compte = 0
lenListe = len(liste)
for i in range(0, lenListe):
if (liste[i] >= n):
compte += 1
return compte
def premiersNa2N(n):
#liste1 = eratostene(n*2)
#compte = compteInfN(liste1, n)
liste2 = crible_G(n)
print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
#print("> N / log(2N) = " + str(n / math.log(2 * n)))
#print("> Pi(2N) = " + str(len(liste1)))
print("> Estimation du TNP Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
print("> Estimation Pi(2N)-Pi(N) = N/log(2N) = " + str(n / math.log(2*n)))
#print("> Avec eratosthene: On compte " + str(len(liste1)-compte) + " nombres premiers entre 1 et " + str(n))
#print("> Avec eratosthene: On compte " + str(compte) + " nombres premiers entre "+str(n)+" et " + str(n*2))
print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
# print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
# print(liste2)
et ne garder que les quatre ligne
print("> Estimation du TNP Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
print("> Estimation Pi(2N)-Pi(N) = N/log(2N) = " + str(n / math.log(2*n)))
print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
jusqu'à la deuxième partie, la fonction :
def crible_G(n):
...etc...
...etc
#645 Re : Programmation » crible en python » 22-01-2018 17:27:19
Re,
Attention si tu as remplacé ta fonction par la mienne (pas une bonne idée, trop lente), il faut déjà que partout dans ton programme où il est écrit eratostene sans h, tu rajoutes le h...
Tu l'as bien fait ?
ok donc il faudrait que je remplace la première fonction d'eratostène sans h , par la tienne ci dessous
nombres, premiers = [],[]
for i in range(2,n+1):
nombres.append(True)
for i in range(2,n+1):
if nombres[i-2]:
premiers.append(i)
for j in range(2*i,n+1,i):
nombres[j-2] = False
return premiers
n=1000
nn=int((2*n)**0.5)
premiers = eratosthene(n)
print(premiers)
et qu'ensuite je mette un h à ératosthène la où il n'y est pas y compris dans la parti crble_g ...?
Ah, ça travaille sous dos !!!
Alors dans ce cas, si tu as recopié mon prog, rajoute à la fin, le input() du tien. Relance et dis-moi si c'est ça...
Son rôle est d'empêcher - sous DOS - la fenêtre de se fermer : avec l'IDLE de Python sous Windows, c'est inutile, je l'avais supprimé
@+
si je copie ta fonction ci dessus, et pas la totalité de ton programme, il y a le input() à la fin du prog..
avec ta fonction je remplace toutes cette partie ? :
n = int(n)
m = (n-1) // 2
b = [True]*m
i = 0
p = 3
premiers = [2]
while p*p < n:
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i += 1
p += 2
while i < m:
if b[i]:
premiers.append(p)
i += 1
p += 2
return premiers
def compteInfN(liste, n):
compte = 0
lenListe = len(liste)
for i in range(0, lenListe):
if (liste[i] >= n):
compte += 1
return compte
#646 Re : Programmation » crible en python » 22-01-2018 17:03:08
ton dernier post de 16h38 : effectivement je n'avais pas compris que tu parlais du h d'Eratosthène
est ce que ça veut dire que dans mes deux programme "Pycharme " il faut que je mette le h dans tous les Eratosthène, où il ne figure pas...et ensuite ...?
que dois faire le programme :
on rentre la valeur n,
on fait appel à eratosthène pour cribler de 1 à [tex]\sqrt{2n}[/tex] pour obtenir les premiers [tex]P_i\leqslant\sqrt{2n}[/tex] qui vont être utilisé par le crible_G à partir de la:
nombres = n*[1]
nombres[0] = 0
p = eratostene(math.sqrt(2*n))
lenp = len(p)
r = []
for i in range(lenp):
..etc..
le programme fait la liste des entiers naturels de 1 à n , représenté par des 1
exemple n = 1000:
donc chaque 1 est un entier 1,2,3........n.
eratosthène à extrait les premiers [tex]P_i\leqslant\sqrt{2n}[/tex] donc < à 44.
soit la liste des $P_i$ : {2.3.5.7.11.13.17.19.23.29.31.37.41.et 43}
le crible_g va utiliser ces $P_i$ : pour calculer le reste R de 2000 par chaque $P_i$ .
Soit les R = {0.2.0.5.9.11.11.5.22.28.16.2.32 et 22}
le crible _g va donc cribler les entiers représentés par 1, $\equiv{2n} [P_i]$ selon le même principe qu'Ératosthène , mais en partant du reste R de 2n Par Pi. On marquera donc tous les entiers non nul de 1 à n, qui sont égaux modulo Pi avec 2n , c'est à dire qui partagent le même reste R modulo Pi
("si il n'y a pas R = 1, alors 2n -1 est premier, donc le premier 1 ne peut être remplacé par 0 et de la même façon si R = 0 on part directement de $P_i$")
sinon on part de R.
le premier couple R + P_i est : (0 ; 2) on part donc du deuxième entier = $P_i = 2$ que l'on marque 0, puis tous les 2 nombres...
le deuxième couple R + P_i est : (2 ; 3) on marque donc le deuxième entier d'un 0, puis tous les 3 nombres...
le troisième couple R + P_i est : (0 ; 5) on part donc du cinquième entier =$ P_i = 5$ que l'on marque 0, puis tous les 5 nombres
le quatrième couple R + P_i est : (5;7) on part donc du cinquième entier que l'on marque 0, puis tous les 7 nombres
le cinqième couple R + P_i est : (9;11) on marque donc le neuvième entier d'un 0, puis tous les 11 nombres
....etc...
A la fin on compte les 1 les entiers qui ne sont congrus à 2n mod P_i, donc: qui donnent les nombres premiers q entre 1000 et 2000
puisque si un entier A de 1 à n est non congrus à 2n[Pi], il ne partage pas le même reste R avec 2n, par conséquent Pi ne divise pas cette différence tel que 2n - A, alors 2n - A est un nombre premier q . Tout entier < 2n, non divisible par un nombre premier Pi < racine de 2n, est un nombre premier : selon Ératosthène.
C'est tout simplement le crible d'eratosthène mais dans les congruences , au lieu de partir de P_i pour barrer leurs multiples, on part de R et on barre tous les congruents de P_i....Voila....
#647 Re : Programmation » crible en python » 22-01-2018 15:39:04
Re,
Mon programme = ?
La totalité ou seulement la fonction eratosthene (celle avec un h) ?
au début la totalité, puis
j'ai copié ceci à la place de la mienne jusqu'à return premier :
nombres, premiers = [],[]
# n=int((2*n)**0.5)
for i in range(2,n+1):
nombres.append(True)
for i in range(2,n+1):
if nombres[i-2]:
premiers.append(i)
for j in range(2*i,n+1,i):
nombres[j-2] = False
return premiers
je n'arrive pas à le lancer
Qu'est-ce que tu entends par là ?
le fenêtre dos , apparait, je rentre la valeur n = 30000000, puis entrée..
la fenêtre se ferme..
Ce programme doit fonctionner sur Pycharm aussi.
Je le testerai plus tard avec. Je vais retourner à ma mise à jour...
[/Parenthèse]
ok
Je t'ai déjà demandé, c'est Pycharm qui a décidé d'une indentation de 2 caractères, alors que c'est 4 recommandé ?
Aucune idée..., je lui ai demandé de cribler avec eratosthène uniquement jusqu'à [tex]\sqrt{2n}[/tex], ce qu'il n'a pas fait...
Moi je travaille avec 4, peut-être que Pycharm n'aime pas le mélange des deux ?
Il faut que j'aille voir...
Je viens de le charger, j'ai regardé vite fait les exemples du site.
J'ai une réponse : l'indentation standard de Pycharm est bien de 4 caractères...
Alors pourquoi 2 ? Choix délibéré du petit-fils ? Dans ce cas mauvaise idée pour la lisibilité...
je ne saurait te répondre car pour moi c'est le brouillard total...., et je ne sais pas pourquoi il a fait ce choix...je vais essayer de t'expliquer ce que doit faire le programme complet post suivant...
@+
#648 Re : Programmation » crible en python » 22-01-2018 14:35:59
voici le lien pour les tests cribl_G et crible_mod30 avec les temps en seconde .
https://www.cjoint.com/c/HAwnHvbeTpW
#649 Re : Programmation » crible en python » 22-01-2018 14:30:26
Autrement dit lorsque l'on modifie la ligne
par :
cela ne peut pas marcher car on devrait avoir pour n = 1000, 2n = 2000; [tex]\sqrt {2000}[/tex], 14 premiers < 44, et non 18...
il y a peut être une solution:
demander à Eratosthène de cribler jusqu'à sqrt de n, et pour crible _g jusqu'à n....rentrer deux valeur de n = 44 pour Eratosthène , et 1000 pour crible_G
ou alors il faut que Eratosthène crible bien uniquement jusqu'à la partie entière de [tex]\sqrt {n}[/tex] et on rentre bien la valeur de n au départ...
bonne journée
#650 Re : Programmation » crible en python » 22-01-2018 14:16:58
Bonjour,
Les listes fournies font suite à ta remarque : "Le but de ... n'est pas..."...
J'ai répondu à la question (que tu n'as pas posée) :
que fait la fonction eratostene() ?
La fonction Eratosthène doit extraire les nombres premiers [tex]P_i\leqslant\sqrt{2n}[/tex] donc [tex]P_i\leqslant\sqrt{2000} = 44[/tex]
c'est tout ce qu'elle doit faire, pour utiliser ces [tex]P_i\leqslant 44[/tex] dans la fonction du crible _G...ci dessous
def crible_G(n):
nombres = n*[1]
nombres[0] = 0
p = eratostene(n)
lenp = len(p)
r = []
for i in range(lenp):
r.append(2*n % p[i])
j = r[i]
while j <= n:
nombres[j-1] = 0
j += p[i]
premiers = []
print("√2N = "+str(int(math.sqrt(2*n))))
for i in range(n-1, 0, -1):
if nombres[i] == 1:
premiers.append(2*n-i-1)
# on regarde si il y a un reste égal à 1
resteUn = 0
lenr = len(r)
for i in range(lenr):
if r[i] == 1:
resteUn = 1
# si aucun reste n'est égal à 1 2*n-1 est premier
if resteUn == 0:
premiers.append(2*n-1)
return premiers
#n = int(input("Donnez la valeur de N : "))
n=1000
print ("Avec ta fonction eratostene :")
print(eratostene(1000))
print("\nAvec ma fomction eratosthene qui est bien le ctible d'eratosthène")
print (eratosthene(1000))
#premiersNa2N(n)
Je t'ai dit simplement que j'appelle :
eratostene (1000) ou eratosthene(1000), les deux fonctions me fournissent la même liste des nombres premiers inférieurs à 1000 (ou à 44 si j j'enlève le # devant n=int((2*n)**0.5) : 44 = partie entière de [tex]\sqrt{2000}[/tex]).
Ok
Si je supprime les lignes ajoutées et le # devant la dernière ligne, que je remets un # devant n=int((2*n)**0.5), je lance le programme, affichage (cohérent) que ce soit avec la fonction eratostene ou la mienne eratosthene :
Ce qui est logique, puisque Eratosthène va cribler jusqu'à n et 2n, étant donné qu'il n'est pas limité à la [tex]\sqrt{2n}[/tex]
Par contre, si j'utilise n= int((2*n)**0.5) dans la fonction eratostene ou la mienne eratosthene, j'obtiens l'affichage qui m'a fait sursauter :
Je pense que l'explication est : Eratosthène ne crible pas jusqu'à n ni jusqu'à 2n; mais uniquement jusqu'à la racine de 2n pour utiliser ces nombres premiers dans le crible_G, donc il extrait bien les premiers [tex]P_i\leqslant 44[/tex].
car comme tu l'as remarqué, le crible _G a bien criblé les congruents à Pi puisqu'il donne bien 135 premiers de 1000 à 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000
donc le résultat d'Eratosthène on ne s'en occupe pas, et il faut mettre # devant les lignes concernées afin qu'il n'écrive pas le résultat...
qui me montre que n= int((2*n)**0.5) produit selon moi des résultats incohérents, que ce n'est pas ce qu'il faut faire.
c'est peut être le cas...Mais si je lance mon programme et que je modifie la ligne n = int(n) par la tienne n= int((2*n)**0.5). je n'obtient pas les bonnes valeurs pour 1000 oui mais pour 30 000 000 voila les vraies valeurs:1 704 256 entre 30 000 000 et 60 000 000
Je te remercie de ton implication.
je vais changer la valeur de la ligne 4 , je refais le test jusqu'à 30 000 000 le résultat obtenu est :3 440 913 , c'est à dire le double..???
Ps: j'ai copié ton programme que j'ai collé dans pycharme je n'arrive pas à le lancer ....avec mon appli ...
@+