Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#51 20-03-2018 13:11:35

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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 17:36:16

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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 10:32:35

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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:

 if j % 30 == 1[0]:

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 10:38:28)

Hors ligne

#54 21-03-2018 11:59:58

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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 :

# 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]:

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#55 21-03-2018 12:48:25

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : crible en python

yoshi a écrit :

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 :

# On elimine les restes pairs
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 13:06:43

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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

# 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]

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 :

# On elimine les restes pairs
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 13:30:57)

Hors ligne

#57 21-03-2018 13:54:31

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Salut,

Ah, j'ai vu...

if d_c in ['0','2','4','6','8']:

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 15:02:11

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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 11:31:20

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : crible en python

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

# On elimine les restes pairs
      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 11:34:14)

Hors ligne

#60 26-04-2018 09:03:17

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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 à

f = j + p*30

ligne que j'ai rajouté...
d'où la ligne

wile j <= f:

que j'ai modifiée.

Avec deux fonctions que j'ai rajoutés

print (j)  et  print (nombres)

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 09:08:17)

Hors ligne

#61 26-04-2018 11:28:51

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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 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 = 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 13:24:48

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : crible en python

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

programme

  ...??? 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

 Donnez la valeur de N = 30k : 150
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

2n%p[i]

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

R[i] et les p[i]

ok je comprend ta surprise .....

5) je recopie le code dans pycharm ci-dessous

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
  #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 

R[i] et les p[i]

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

r[i] et les p[i]

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

je reviens...voila l'instrucstion ok

 p= eratostene(int(n))[3:]

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

 pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        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 14:11:05)

Hors ligne

#63 26-04-2018 13:50:42

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : crible en python

Je crois avoir trouvé mon erreur dans ta réindentation ; j'ai oublié la ligne 83 , j'ai laissé

d_c = str(j)[-1]

au lieu de d_c = j%10
je recommence...

Hors ligne

#64 26-04-2018 13:54:11

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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 13:57:57

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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 14:08:03

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : crible en python

yoshi a écrit :

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

#67 26-04-2018 16:43:38

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : crible en python

Bonsoit,

Le problème ne vient pas de là !

Je regarde...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#68 26-04-2018 16:50:46

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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 18:51:14

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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 21:46:45

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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']..

pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        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

 j += incr
    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...

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")

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 06:43:42)

Hors ligne

#71 27-04-2018 06:57:22

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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 07:57:52

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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:

elif d_c == '3':  # on vérifie 13 et 23
        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

elif d_c == '1':  # on vérifie 1 et 11
        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

# On elimine les restes pairs
        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 08:07:55

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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 08:21:05)

Hors ligne

#74 27-04-2018 15:20:23

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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 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(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 16:06:56

LEG
Membre
Inscription : 19-09-2012
Messages : 690

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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
cinquante quatre moins vingt
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums