Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#51 20-03-2018 14:11:35
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Salut,
J'ai fait 2 tests:
================= RESTART: C:/Python35/Progs persos/v3.x/Ctible premiers LEG.py =================
Donnez la valeur de N = 30k : 30
Crible mod30 : Initialisation: 0.0 seconds ---
Crible mod30 : Famille de chaque Pi: 0.0 seconds ---
Crible mod30 : Criblage des 8 familles: 0.0 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---
On a 0 nombres premiers
>>>
================= RESTART: C:/Python35/Progs persos/v3.x/Ctible premiers LEG.py =================
Donnez la valeur de N = 30k : 60
Crible mod30 : Initialisation: 0.0 seconds ---
Crible mod30 : Famille de chaque Pi: 0.0 seconds ---
Crible mod30 : Criblage des 8 familles: 0.0 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---
On a 8 nombres premiers
>>>
Ce qui est faux dans les deux cas:
De 30 à 60, il y a 6 nombres premiers : [31, 37, 41, 43, 47, 53, 59]
De 60 à 120, il y a 13 nombres premiers et non 8 : [61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
Alors ?
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#52 20-03-2018 18:36:16
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
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 ...
Hors ligne
#53 21-03-2018 11:32:35
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour
@Yoshi ,il se pourrait que l'erreur vienne de cette ligne d'instruction :
# 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':
car effectivement si le reste R de 2n par Pi est pair on n'a pas besoin de vérifier le modulo de la famille concernée ; mais par contre on part bien de ce reste R auquel on rajoute Pi, et on vérifie si la terminaison correspond bien à l'une des 8 familles concernées et si il est bien congru à Pi modulo 30 pour la famille concernée; ou 1 modulo 30 pour la famille 1 [30].
par exemple , j'ai pris N= 300 et je veux cribler la famille 1[30] . [tex]\sqrt{600} = 24,...[/tex]
les [tex] P_i = 7.11.13.17.19.23[/tex] les [tex]R_i = 5 . 6.2.5.11.2[/tex]
initialisation et criblage de la famille 1[30] cela va nous donner dix nombres [1].
et le criblage va marquer 61 et 271. soit le troisième nombre et le dixième;"qui corresponde à la cellule N°2 et 9"
[tex][1].[1].[0].[1].[1].[1].[1].[1].[1].[0][/tex] extraction, on a bien 8 nombres premiers. (" de n à 2n pour la famille complémentaires à 1[30] soit la famille 29[30]...") qui sont [tex]359.389.419.449.479.509.569.599[/tex] ça on a pas besoins de l'écrire , car on compte que les nombres [1] lors de l'extraction.
mais lors du criblage on voit bien que si les restes R sont pairs, on rajoute P_i si il ne se termine pas par 1 on rajoute ensuite 2*P_i donc impair et si il se termine par 1 on vérifie le "modulo" : qu'il est bien congru à 1[30] ; sinon on continue jusqu'à la limite n = 300...puis on passe au [tex]P_i[/tex] et son[tex]R_i[/tex] suivant...etc
En exemple pour ce cas ; pour [tex]P_i = 11[/tex] et son [tex]R_i = 6[/tex]. On part du reste :
6 + 11 ; 17 +22 ; 39+22 = 61 on vérifie le modulo c'est à dire la ligne de code:
donc ok.
On le place dans sa famille à sa position :
(61-1)/30 = 2 cell N° 2, le troisième [1].
Ensuite on marquera tous les 11[1] jusqu'à la lim N = 300.
Dans cet exemple, on a que le troisième c'est à dire le N°2, [1] = [0] ;
"car on compte en commençant par 0,1,2,....n"
j'espère que cela correspond bien aux lignes d'instruction du crible_mod30.....???
Dernière modification par LEG (21-03-2018 11:38:28)
Hors ligne
#54 21-03-2018 12:59:58
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Salut,
J'ai de nouveau un coup de bourre :
litige avec un syndic à régler et fin de nettoyage de l'appart' de ma mère en vie d'une location.
J'y réfléchis entre deux...
Déjà, ça (ce n'est pas une erreur) c'est inutile :
if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
il vaut mieux écrire :
if d_c in [0,2,4,6,8]:
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#55 21-03-2018 13:48:25
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Salut,
Déjà, ça (ce n'est pas une erreur) c'est inutile :# 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':il vaut mieux écrire :
# On elimine les restes pairs
if d_c in [0,2,4,6,8]:@+
oui mais est ce que l'instruction :
if d_c in [0,2,4,6,8]:
veut dire que l'on ne calcule pas le modulo, donc on rajoute au reste R, [tex]P_i[/tex] qui deviens [tex]J_i[/tex] je suppose....Puis on vérifie si il se termine bien par la famille que l'on a choisie par ex : 1 (modulo30) si oui, on vérifie le modulo: 1[30] = 0 ; sinon on rajoute 2*P_i...etc
juqu'à ce que l'on tombe sur la terminaison par 1...ou 3 ..ou 7...ou 9. < à la lim N définie en entrée; afin de vérifier le modulo en question et de le placer dans sa famille pour commencer le criblage jusqu'à la limite N définie...
car si on élimine les restes R pairs purement et simplement on part de où...? je suppose que ce n'est pas le cas car le crible serait faux même pour une petite limite ...
On aurait n'importe quoi ce qui n'est pas le cas à partir de N =1500....même 600 il suffit de rajouter 30 soit 630 qui donne la bonne valeur que crible_G(n) à une exception près à cause du 1...
donc par rapport à ta réflexion je suppose que ce n'est qu'une mauvaise écriture...que je vais vérifier et modifier cette ligne...
A+
Hors ligne
#56 21-03-2018 14:06:43
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
je viens de modifier la ligne en question, et cela provoque une erreur pour N = 600 j'ai :98 n primes au lieu de 87, j'augmente de 30 j'en ai 108 au lieu de 91....?
alors qu'avec l'ancienne ligne
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]
j'ai 85 pour N =600 et 90 pour N = 630 soit un écart de 1 par rapport à crible_G(n)...
peut être qu'avec cette ligne :
if d_c in [0,2,4,6,8]:
il faut modifier les lignes d'instruction dessous...???
D'autant que la phrase : # On elimine les restes pairs prête à confusion , car on aurait dû écrire :
#si le reste est pair on ajoute directement Pi et on verifie
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:
Dernière modification par LEG (21-03-2018 14:30:57)
Hors ligne
#57 21-03-2018 14:54:31
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Salut,
Ah, j'ai vu...
On élimine les restes pairs, j'attendais des nombres, et il fallait voir des strings...
Non, rien à changer après, j'ai juste fait en sorte d'avoir une ligne plus courte et plus rationnelle...
Quid de d_c=="10", d_c=="12", d_c=="14"... etc... ? 10, 12, 14... sont aussi des nombres pairs.
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#58 21-03-2018 16:02:11
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Ok yoshi
je viens de la remplacer c'est bon ...
tout à l'heure je l'ai fait mais j'ai dû mal placer les ' ' , car ça ne changeait rien...
"c'est la terminaison paire qui est pris en compte" c'est pour cela que le crible passe directement à l'étape suivante en rajoutant [tex]P_i[/tex]
de même si la terminaison se termine par '5'..on ajoute [tex]2*P_i [/tex] on passe au suivant..on ne teste pas le modulo.
il faut que [tex]R_i[/tex] ou [tex]j_i + 2*P_i[/tex] se termine par 1, 3, 7 ou 9 si on crible les 8 familles ce qui n'est pas le but..
C'est pour cela qu'il faut travailler uniquement par Famille plus simple à programmer et plus rapide , ainsi que dans l'exécution de l'algorithme cela utilise moins de mémoire et donc la limite est plus grande...
Ce qui permet aussi de voir pourquoi on a une même densité de premiers de n à 2n par Famille.
Le travaille est le même quelque soit la limite N par Famille..
le criblage des [tex]P_i[/tex] est le même, seul la position de départ va légèrement changer, mais n'aura aucune incidence sur la densité de nombres premiers par famille, que ce soit le crible de 7 à N ou de N à 2N ...
Hors ligne
#59 02-04-2018 12:31:20
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour
@Yoshi
voici ce bloc d'instructions qui me pose question:
if d_c in ['0','2','4','6','8']:
j += p[i]
d_c = str(j)[-1]
[b]while j < n:[/b]
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
la commande while j < n: veut bien dire que l'on ajoute p(i) à J jusqu'à n , et j = r(i)
dans le bloc d'instructions ci-dessus
# 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]
Mais normalement il ne devrait pas y avoir une autre instruction: 1) tel que on ajoute p(i) jusqu'à d_c == '1' et et on vérifie le (modulo)1%30 ou 11%30 = 0 , ou jusqu'à < n
c'est à dire : while J % 30 == p8[0] , ou < n:
exemple:
Exemple de crible N = 150 , Pi < sqrt 300 = {7;11;13 ; 17 } ; reste R de 300 par les Pi : R = {6; 3 ; 1; 11} . 150 /30 = 5 cell par Famille.
Pi = 7 et R = 6 , ce qui va donner : 6 +7 = 13 ; → +14 = 27 → +14 = 41→ +14 = 55 → +14 = 69→ +14 = 83→ + 14 = 97→ +14 =111
→ +14 = 125 → +14 = 139 → +14 =153 > n = 150 fini pour Pi = 7 qui ne crible que 5 Famille sur 8.
Pi = 11 et R = 3
3 +( 2*11) → +22 = 47 → +22 → +22 = 91 = 1%30 et (91 -1)/30 = cell N°3
Pi = 13 et R = 1
1 = 1%30 et (1-1)/30 = cell N°0
Pi = 17 et R = 11
11 + 34 → +34 →+34 →+34 > n fin
(« Si on choisit de cribler par Famille et on choisit la Famille 1[30] . Pi = 7 ne marque aucune cellule dans cette famille. Pi = 11 et R =3 , va marquer 91 cell N°3 , puis sort du crible ; Pi = 13 et R = 1 , va marquer la cell N° 0 donc la première le [1] devient [0], puis Pi = 13 sort ; et Pi = 17 et R = 11 ne marquerait que la famille 11[30], et sort »)
initialisation
0 1 2 3 4
1 ; 1 ; 1 ; 1 ; 1
criblage
0 1 2 3 4
0 ; 1 ; 1 ; 0 ; 1
A moins que cela se fasse automatiquement dans le programme, c'est à dire que j < n est la limite maximum ....
("Mais je n'arrive toujours pas à modifier pour ne travailler que dans une famille, exemple la famille 1 (modulo 30)...")
Dernière modification par LEG (02-04-2018 12:34:14)
Hors ligne
#60 26-04-2018 10:03:17
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour
est ce qu'il y a une limite dans python, car voici les différentes valeurs de 30k extrait de la fenêtre cmd :
Donnez la valeur de N = 30k : 3000000000
Crible mod30 : Famille de chaque Pi: 6.084010362625122 seconds ---
Crible mod30 : Criblage des 8 familles: 185.3283257484436 seconds ---
On a 135095831 nombres premiers n à 2n
Donnez la valeur de N = 30k : 3420000000
Crible mod30 : Famille de chaque Pi: 45.474079847335815 seconds ---
Crible mod30 : Criblage des 8 familles: 382.5750720500946 seconds ---
On a 153107189 nombres premiers n à 2n
Donnez la valeur de N = 30k : 3540000000
Crible mod30 : Famille de chaque Pi: 7.784413576126099 seconds ---
Crible mod30 : Criblage des 8 familles: 221.55158925056458 seconds ---
On a 158233655 nombres premiers n à 2n
Donnez la valeur de N = 30k : 3660000000
Crible mod30 : Famille de chaque Pi: 19.172433853149414 seconds ---
Crible mod30 : Criblage des 8 familles: 244.10922861099243 seconds ---
On a 163351999 nombres premiers n à 2n
Donnez la valeur de N = 30k : 3690000000
Crible mod30 : Famille de chaque Pi: 30.310853481292725 seconds ---
Crible mod30 : Criblage des 8 familles: 241.78482460975647 seconds ---
On a 164630426 nombres premiers n à 2n
Donnez la valeur de N = 30k : 3720000000
Crible mod30 : Famille de chaque Pi: 30.342053174972534 seconds ---
Crible mod30 : Criblage des 8 familles: 369.8454496860504 seconds ---
On a 165910122 nombres premiers n à 2n
Limite atteinte , pour 3750000000 il initialise, calcule les j = R pour Famille de chaque Pi :
44 seconde environ…puis tourne sans arrêt…donc il ne crible plus les 8 familles
????
j'ai modifié le code ci dessus
par celui ci-dessous, car il y avait une erreur ligne 50 que j'ai rajouté et ligne 57 que j'ai modifié , car il calculer les j = R jusqu'à la limite n au lieu de se limiter à
ligne que j'ai rajouté...
d'où la ligne
que j'ai modifiée.
Avec deux fonctions que j'ai rajoutés
que l'on peut activer ou non...
Ce qui a eut pour résultat de ne pas faire d'erreurs de nombres premiers de n à 2n pour de petites valeur de k *30 = 105...120...150...etc et de diviser le temps d'exécution par 5...
import os
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:
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:
premiers.append(p)
i += 1
p += 2
#print(premiers)
return premiers
# 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
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 = []
# FAMILLES POUR CHAQUE Pi
start_time = time.time()
for i in range(lenp):
r.append(2*n % p)
pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
j = r
f = j + p*30
incr = p*2
d_c = str(j)[-1]
# si la terminaison du reste est pair on ajoute directement Pi et on verifie
if d_c in ['0','2','4','6','8']:
j += p
d_c = str(j)[-1]
while j <= f:
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[fam] == 0:
pfam[fam] = j
j += incr
d_c = str(j)[-1]
#print(j)
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[j] - p8[j]) / 30)
while index < nbcell:
nombres[j][index] = 0
index += p
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:
if cell == 1:
count += 1
# CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
premiers = []
for i in range(8):
for j in range(nbcell-1, -1, -1):
if nombres[j] == 1:
premiers.append(nombres[j] == 1)
#print(nombres)
premiers.sort()
return premiers
n = int(input("Donnez la valeur de N = 30k : "))
nb = len(crible_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
import os
import math
import time
l'idéal, restant toujours le criblage uniquement par famille....
Dernière modification par LEG (26-04-2018 10:08:17)
Hors ligne
#61 26-04-2018 12:28:51
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Salut,
Je te répète encore :
1. Utilise les balises code et /code : symbole sur barre d'outils <>
2. Respecte les recommandations de Python concernant l'indentation. Si c'est Pycharm qui indente de deux caractères, c'est un mauvais point pour lui.
J'ai passé 1/2 h à tout réindenter...
3. N'utilise pas des clés comme noms de variables, c'est malsain :
count et index sont des méthodes.
Exemple :
L= ['R', 'e', 's', 'p', 'e', 'c', 't', 'e', 'l', 'e', 's', 'r', 'e', 'c', 'o', 'm', 'm', 'a', 'n', 'd', 'a', 't', 'i', 'o', 'n', 's', 'd', 'e', 'P', 'y', 't', 'h', 'o', 'n', 'c', 'o', 'n', 'c', 'e', 'r', 'n', 'a', 'n', 't', 'l', 'i', 'n', 'd', 'e', 'n', 't', 'a', 't', 'i', 'o', 'n']
L. count("e") renvoie 8.
L.index("P") renvoie 28 : le "P" est en 29e position --> L[28] renvoie "P"
Ceci ton prog plante ici : r.append(2*n % p).
Pycharm accepte ça ?
2*n est un entier et p une liste...
Voilà le message d'erreur :
Traceback (most recent call last):
File "<pyshell#9>", line 1, in <module>
r.append(2*n % p)
TypeError: unsupported operand type(s) for %: 'int' and 'list'
Il dit que tu ne peux pas chercher le reste de la division d'un nombre par une liste, il y a incompatibilité.
Je présume que tu voulais écrire 2*n % p[indice] quel indice.
J'ai fait qq modifs qui devraient accélérer le programme
Le chiffre des unités d'un nombre j s'obtient par j%10 plus rapide que str(j)[-1]
Après, le test :
if d_c in ['0','2','4','6','8']:
j += p
d_c = str(j)[-1]
s'écrit :
if d_c % 2 ==0
j += p
d_c = j%2
Mais ça aussi c'est problématique : j += p
Comment peut-on ajouter un liste p à un nombre j ?
Tu peux combiner :
p = eratostene(int(n))
p = p[3:] -
en :
p= eratostene(int(n))[3:]
Réindenté et entre balises code \code, c'est bien plus lisible...
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:
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:
premiers.append(p)
i += 1
p += 2
print(premiers)
return premiers
# 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
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 = []
# FAMILLES POUR CHAQUE Pi
start_time = time.time()
for i in range(lenp):
r.append(2*n % p)
pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
j = r
f = j + p*30
incr = p*2
d_c = j%10
# si la terminaison du reste est pair on ajoute directement Pi et on verifie
if d_c %2==0:
j += p
d_c = j%10
while j <= f:
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[fam] == 0:
pfam[fam] = j
j += incr
d_c = j%10
#print(j)
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[j] - p8[j]) / 30)
while index < nbcell:
nombres[j][index] = 0
index += p
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:
if cell == 1:
count += 1
# CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
premiers = []
for i in range(8):
for j in range(nbcell-1, -1, -1):
if nombres[j] == 1:
premiers.append(nombres[j] == 1)
#print(nombres)
premiers.sort()
return premiers
n = int(input("Donnez la valeur de N = 30k : "))
nb = len(crible_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
Je continue après...
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#62 26-04-2018 14:24:48
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour Yoshi....
1) pourtant, je les ai rentrée les balises
...??? je vais modifier le message ci-dessus
2) c'est surement un mauvais point pour mon petit fils , je fais ce que je peux pour modifier certaine ligne mais je ne comprend pas Pycharm en plus c'est en anglais...
3)je viens de faire un copie collé de ton programme réindenté dans Pycharme , je lance et ça ne marche pas la fenêtre cmd se ferme directement...
voila ce que donne avec l'indentation d'avant:
extrait
Crible mod30 : Famille de chaque Pi: 0.0 seconds ---
Crible mod30 : Criblage des 8 familles: 0.0 seconds ---
On a 27 nombres premiers
Appuyez sur une touche pour continuer...
4) dans mon programme c'est
et non 2n%p
c'est mon copié collé entre les balises code qui m'enlève les
ok je comprend ta surprise .....
5) je recopie le code dans pycharm ci-dessous
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
#print(premiers)
return premiers
# 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
nbcell = int(n/30)
nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
p = eratostene(int(n))[3:]
lenp = len(p)
r = []
p8 = [1, 7, 11, 13, 17, 19, 23, 29]
pfam = []
# 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]
f = j + p[i]*30
incr = p[i]*2
d_c = str(j)[-1]
# si la terminaison du reste est pair on ajoute directement Pi et on verifie
if d_c in ['0','2','4','6','8']:
j += p[i]
d_c = str(j)[-1]
while j <= f:
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(j)
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
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(nombres)
premiers.sort()
return premiers
n = int(input("Donnez la valeur de N = 30k : "))
nb = len(crible_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
ok je viens de vérifier les
sont bien restés...
7) donc je vais modifier les lignes que tu m'as indiquées...et je fais un test je comprend aussi pourquoi en recopiant ton indentation ça ne marchais pas puisque les
ont été supprimés , d'où ta surprise que ça pouvait fonctionner dans Pycharm alors que non !...
je reviens...voila l'instrucstion ok
Mais cette partie là ci-dessous génère une erreur dans le criblage...je t'ai mis le i devant les r et les p
j = ri
f = j + pi*30
incr = pi*2
d_c = j%10
# si la terminaison du reste est pair on ajoute directement Pi et on verifie
if d_c %2==0:
j += pi
d_c = j%10
while j <= f:
Dernière modification par LEG (26-04-2018 15:11:05)
Hors ligne
#64 26-04-2018 14:54:11
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Salut,
Ah oui les fameux [ i ], ça me revient...
Le moteur du forum les interprète comme de l'italique. J''avais trouvé deux solutions :
- utiliser une autre lettre,
- soit doubler le i : r[ii] , p[ii]
Dans ton script, les restes d_c ne sont bien jamais > 10 ?
Je vais voir ma mère, dans sa maison de retraite et repenser à mon retour au pourquoi des erreurs dans le crible...
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#65 26-04-2018 14:57:57
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
je viens d'essayer c'est pire au lieu de 28 nombre , j'en ai 31 , pou n =150
Donnez la valeur de N = 30k : 150
Crible mod30 : Famille de chaque Pi: 0.0010001659393310547 seconds ---
Crible mod30 : Criblage des 8 familles: 0.0 seconds ---
On a 27 nombres premiers
Appuyez sur une touche pour continuer...
Hors ligne
#66 26-04-2018 15:08:03
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Salut,
Ah oui les fameux [ i ], ça me revient...
Le moteur du forum les interprète comme de l'italique. J''avais trouvé deux solutions :
- utiliser une autre lettre,
- soit doubler le i : r[ii] , p[ii]Dans ton script, les restes d_c ne sont bien jamais > 10 ?
@+
dans le programme si on prend bien les balise <code> et </code> ça reste bien R<i> et P<i>...puisque je l'ai refait...
pour les décimales d_c ça ne peut pas être > 10 c'est toujours une terminaison de ['0'....à '9']
j'ai donc remis comme avant d-c ['0', '2', '4' , '6' , '8']
et
d_c = str(j)[-1]
@+ et merci Yoshi.
Hors ligne
#68 26-04-2018 17:50:46
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
pour qu'il n'y ait pas confusion :
p Eratosthène est la liste des premiers > 5 et [tex]<\sqrt{2n}[/tex]
p['i'] est un nombre premier appartenant à p
R est les reste de la division de 2n par p['i']
R['i'] est le R + p['i'] si R est pair ou R + 2*p['i'] pour R impair , donc les j = R['i']
On calcule les j jusqu'à la limite < (R + p['i']) + p['i']*30, c'est à dire j + p['i']*30
car sinon si on avait mis : Wile j < n et bien cela aurait calculer tous les j inférieur à n ce qui est absurde puisque l'on a besoins que de la position de j par Famille, donc des 8 j, un par Famille; pour chaque p['i'] , et ensuite , à partir de cette position c'est p['i'] qui crible jusqu'à la limite n/30 et ce, dans chaque famille; puisque l'on travaille dans les familles de raison 30, sauf la première cellule qui vaut : [1,7,11,13,17,19,23, ou 29]
voici un extrait des j = r['i'] pour n = 150.pour les P['i'] = {7,11,13,17} ce qui donne , 15 j, est le 16ème est tout simplement la réitération de j + pi*30
exemple n = 150, pour pi = 7, R= 6, 2n =300, J = 6+7 = Ri = 13 et 13 + 7*30 = 223 qui est le dernier j = ri
pour le suivant pi = 11 ; R = 3 ; j = 3 + 2*pi = 25 ; et 25 +11*30 = 355 qui est la limite wile j < f ligne 57 du programme.
Donnez la valeur de N = 30k : 150
27
41
55
69
83
97
111
125
139
153
167
181
195
209
223
25
47
69
91
113
135
157
179
201
223
245
267
289
311
333
355
27
53
79
105
131
157
183
209
235
261
287
313
339
365
391
417
45
79
113
147
181
215
249
283
317
351
385
419
453
487
521
555
Crible mod30 : Famille de chaque Pi: 0.013000965118408203 seconds ---
Crible mod30 : Criblage des 8 familles: 0.0 seconds ---
On a 27 nombres premiers
Appuyez sur une touche pour continuer...
c'est ok...
@+
Hors ligne
#69 26-04-2018 19:51:14
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Salut,
Ancienne version, réindentée, avec d_c un nombre et j%10.
Elle fonctionne sans planter...
ca m'a pris 1 h à cause d'un pb d'indentation que je n'arrivais pas à trouver.
Cette version donne une fausse valeurs pour n =240 : 35 au lieu de 40.
Demain, je m'attaque à ta nouvelle version et j'entends bien te prouver que le problème n'est pas lié au remplacement de str(j)[-1]
Là, je sature...
import os
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 crible_mod30(n):
# INITIALISATION
start_time = time.time()
nbcell = n//30
nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
p = eratostene(int(n))[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 = j%10
# On elimine les restes pairs
if d_c %2==0:
j += p[i]
d_c = j%10
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 == 1:
fam = 0
else:
fam = 2
elif d_c == 3: # on vérifie 13 et 23
if j % 30 == 13:
fam = 3
else:
fam = 6
elif d_c == 7: # on vérifie 7 et 17
if j % 30 ==7:
fam = 1
else:
fam = 4
else: # on vérifie 19 et 29 (d_c = 9)
if j % 30 == 19:
fam = 5
else:
fam = 7
if fam != -1 and pfam[i][fam] == 0:
pfam[i][fam] = j
j += incr
d_c = j%10
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 : "))
P=crible_mod30(n)
nb = len(P)
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#70 26-04-2018 22:46:45
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
re @Yoshi
tu as changé beaucoup de choses.
while j <=n: #cette ligne est fausse pour de petites valeur je te l'ai expliqué il faut f à la place de 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 == 1: #je l'ai fait ok
fam = 0
else:
fam = 2
elif d_c == 3: # on vérifie 13 et 23
if j % 30 == 13: #je l'ai fait ok
fam = 3
else:
fam = 6
elif d_c == 7: # on vérifie 7 et 17
if j % 30 ==7: #je l'ai fait ok
fam = 1
else:
fam = 4
else: # on vérifie 19 et 29 (d_c = 9)
if j % 30 == 19: #je l'ai fait ok
fam = 5
else:
fam = 7
if fam != -1 and pfam[i][fam] == 0:
il te faut créer une ligne entre: j=r['i'] et incr = p['i']..
j = r[i]
f = j +p[i] * 29 #cette ligne est à ajouter j'ai mis 29 au lieu de 30 car c'est plus précis, voir l'exemple que j'ai cité au post dessus.
incr = p[i]*2
De ce fait tu pourra indiquer la limite de j lorsqu'il construit et positionne les R['i'] pour chaque famille
while j <=f: au lieu de while j <=n:
c'est ce qui créait une erreur de nombres pour des valeur < n = 1500 et de plus multipliait le temps d'exécution par 5
d'ailleurs met la ligne print (j) et tu pourras voir
d_c = str(j)[-1]
print(j)
print("Crible mod30 : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))
pourquoi ces deux lignes à la fin : P=crible_mod30(n) et nb = len(P) au lieu de nb = len(crible_mod30(n)) uniquement
je l'ai fait c'est vrai que cela ne change rien...
P=crible_mod30(n)
nb = len(P)
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
il me reste plus que les trois lignes du remplacement de str(j)[-1] et des ("d_c paire ") que je viens de faire, et ça ne marche pas du tout... pour n = 300 j'ai 62 nombres au lieu de 47....Tu peux d'ailleurs vérifier avec la fonction print(j) les restes j=r['i'] pour n=150 que je t'ai indiqué ....
@+ bonne nuit....
Dernière modification par LEG (27-04-2018 07:43:42)
Hors ligne
#71 27-04-2018 07:57:22
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Re,
pourquoi ces deux lignes à la fin : P=crible_mod30(n) et nb = len(P) au lieu de nb = len(crible_mod30(n)) uniquement
je l'ai fait c'est vrai que cela ne change rien...
C'était pour voir ce qu'il avait dans la liste premiers : rien que des TRUE...
Je savais que cette version avait des pbs, mais je l'avais retouchée, il y a déjà un temps certain (sauf indentation) et je savais qu'elle tournait sans plantage.
Je me suis concentré cette fois sur l'indentation et la simplification des instructions, je vais en faire d'autres et virer tous les petits if.... else et les remplacer par des booleens, par ex
elif d_c == 1: # on vérifie 1 et 11
if j % 30 == 1: #je l'ai fait ok --> Normal, c'est rien d'autre que p8[0]
fam = 0
else:
fam = 2
deviendra :
elif d_c == 1: # on vérifie 1 et 11
fam=2*( j % 30 != 1)
Explications : si j%30 !=1 alors la parenthèse est TRUE qui vaut 1 et 0 dans le cas contraire), fam prend donc les valeurs 2*1 ou 2*0...
Ce devrait être plus rapide...
Quant à 1 au lieu de p8[0], ça épargne à Python d'aller chercher dans sa mémoire la liste p8, puis d'accéder à p8[0] pour en tirer 1.
Je vais déjeuner, puis annuler un RDV pour la voiture de ma fille et je m'y colle....
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#72 27-04-2018 08:57:52
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour
@Yoshi , je viens de vérifier avec ton instruction : d_c = j%10 et d_c 2%==0: au lieu de ['0','2','4','6','8']:
pour n= 150, effectivement les j = r['i] sont les mêmes ...Conclusion, ils doivent être mal positionnés dans leur famille respective...! pour indiquer les mauvaises valeurs : 31 nombre au lieu de 27. Ou alors il occulte le premier r['i]....?
voici ci-dessous les j pour p['i] = 7 et 2n%p['i] = 6 , d'où : j = 6+7=13 et 13 + 2*7 = 27 ; de plus 13 + 7*29 = 223 , qui est bien le dernier j
de ce fait, le programme doit bien positionner les 8 j afférente à leur famille respective...
on a donc j qui appartient au p8 = [1.7.11.13.17.19.23.29]
soit j = [181.97.41.13.167.139.83.209] le 13, même si il est masqué, il est bien pris en compte par le programme, et placé ligne 0 ou le [1] quatrième famille est marqué [0]. Car le bloc de commande qui vérifie la terminaison:
if j % 30 == 13:
Positionne aussi à la bonne place le j= r['i], par le quotient, tel que (13 -13)/30 = 0, donc ligne ou cell n° 0 puis p['i] = 7,à partir de cette position, va cribler c'est à dire marquer d'un[0] tous les 7 nbcell jusquà n/30 = 5 nbcell ...
pour j = 181
if j % 30 == 1:
on a (181 - 1) /30 = 6 donc trop grand il ne peut rien marquer pour n = 150 ...ok
Mais par contre, pour p['i] = 13 ; R = 1 et donc j = 1+26 = 27...etc on aura bien D_c ='1' donc (1 -1) /30 = 0
le [1] nbcell n°0 serra transformer en [0] et 13 va cribler en partant de cette position...
donc voila pourquoi il faut être sûr que les j sont bien positionnés avec la fonction d_c = j%10 ou que
if d_c %2==0:
, ne modifie pas la position de départ de j=['i], dans sa famille...car p['i] ne partira pas de la bonne position d'où erreur dans le décompte...des ncell == [1] et des nombres premiers de n à 2n...
Donnez la valeur de N = 30k : 150
27
41
55
69
83
97
111
125
139
153
167
181
195
209
223
Hors ligne
#73 27-04-2018 09:07:55
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
yoshi Re,
pourquoi ces deux lignes à la fin : P=crible_mod30(n) et nb = len(P) au lieu de nb = len(crible_mod30(n)) uniquement
je l'ai fait c'est vrai que cela ne change rien...
ok Yoshi..
je viens de regarder le reste de ton post , c'est vrai que cela serra plus rapide et plus précis...
donc parfait , en attendant tes instructions afin de modifier "mon indentation dans Pycharm..."
actuellement pour n = 3 000 000 000 , voici le résultat que j'avais :
Donnez la valeur de N = 30k : 3000000000
Crible mod30 : Famille de chaque Pi: 6.084010362625122 seconds ---
Crible mod30 : Criblage des 8 familles: 185.3283257484436 seconds ---
On a 135 095 831 nombres premiers n à 2n
et toujours pour n = 150 voici les j pour p['i] =13 et R = 1 pour 2n%13 ; on a bien j =1 +26 = 27
et j = 1+13*29 indique la limite wile j < f
27
53
79
105
131
157
183
209
235
261
287
313
339
365
391
@+
Dernière modification par LEG (27-04-2018 09:21:05)
Hors ligne
#74 27-04-2018 16:20:23
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 988
Re : crible en python
Salut,
Dernière version corrigée
pour n=12000 m'annonce 1230 premiers : j'ai vérifié, c'est correct...
Tu risques de ne plus y retrouver tes petits (mais j'espère que c'est plus rapide).
1. J'ai supprimé toute ta longue litanie des if elif if else...
2. Pour ce faire, j'ai créé une liste appelée Jmod30 (le nom est transparent) qui peut être allongé avec un p8 deveant p9, p10...:
L'indice que chaque élément de la liste j%30, sa valeur est fam.
(Tu peux remplacer tous les zéros, sauf en Jmod30[1], par None si tu veux...
3. Comme les d_c que tu testais sont forcément impairs:
a) les restes pairs sont écartés
b) que les cas de 3 et 5 étant réglés avant,
je n'ai pas besoin d'autres tests, j'accède directement à la valeur de fam...
4. J'ai remplacé if d_c ==5 par if j%5==0
J'ai aussi vérifié en remplaçant if j%3 ==0 or j%5 ==0 par if j%15==0, ça reste conforme...
A toi de tester, maintenant.
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 crible_mod30(n):
# INITIALISATION
start_time = time.time()
nbcell = n//30
nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
p = eratostene(n)[3:]
lenp = len(p)
r = []
p8 = [1, 7, 11, 13, 17, 19, 23, 29]
pfam = []
Jmod30=[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 3, 0, 0, 0, 4, 0, 5, 0, 0, 0, 6, 0, 0,\
0, 0, 0, 7]
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]
f=j+p[i]*30
incr = p[i]*2
d_c = j%10
# si la terminaison du reste est pair on ajoute directement Pi et on verifie
if d_c %2==0:
j += p[i]
d_c = j%10
while j <= f:
if j%3 ==0 or j%5==0: # on passe au suivant
fam = -1
else:
fam = Jmod30[j%30]
if fam != -1 and pfam[i][fam] == 0:
pfam[i][fam] = j
j += incr
d_c = j%10
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_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system(pause)
Pour Pycharm, j'ai cherché sur Google : j'ai trouvé comment modifier l'indentation d'une ligne, mais je voudrais un fichier de config où je peux fixer l'indentation par défaut à 4...
Je continue à chercher, je l'ai téléchargé. Je vais peut-être être obligé de l'installer.
Dans un de tes posts, tu me demandais s'il y avait une limitation dans Python... A propos de quoi ?
Je connais une limitation ; celle de la quantité de mémoire installée sur ta machine.
Avec 16 Go, je serai probablement limité moins rapidement que toi sur la taille des nombres ou leur quantité...
@+
[EDIT] Regarde voir ce que raconte Pycharm quand tu fais Ctrl+Alt+S
https://www.jetbrains.com/help/pycharm/ … ython.html
Arx Tarpeia Capitoli proxima...
Hors ligne
#75 27-04-2018 17:06:56
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
re @Yoshi
je viens de faire dans Pycharm alt ctrl s
cela m'ouvre une fenêtre écrit en anglais donc je ne sais pas ce que je dois faire ....
je vais copier coller ton indentation je vérifie pour n = 12000 et je met le résultat si ok....
à tout de suite
Hors ligne