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

#101 30-04-2018 16:09:59

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

Re : crible en python

ok Yoshi .
mais je pense qu'il y a un problème à la base d'après ton avant dernier post: au sujet des %3== {0,1, ou2}

pourquoi les énumérer...?

puisque et d'après ce bloc:

#  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if j %2==0:
            j += pi
        while j <=f:
            if j%3!=0 and j%5!=0:              
                fam =Dico[j%30]      
                if pfam[i][fam] == 0:
                    pfam[i][fam] = j
            j += incr
 

on ne fait pas directement


 while j <=f: #on établi les j < f
        j += incr
       if j > f  puis breack

     #on passe à l'étape suivant ("je ne connais pas le rôle de fam dans le programme mais tu vas comprendre")

     if fam =Dico[j%30]      
                if pfam[i][fam] == 0:
                    pfam[i][fam] = j
     else :
 #on passe au j suivant  où est le problème ...donc on ne s'occupe que des 2 conditions en fonction de D_c [1,3,7,9] .
 

Je pense que l'erreur qu'à fait mon petit fils, c'est de vouloir s'occuper de j%3==0 ou D_C ==5
sauf Bien sûr si il y a une raison obligatoire que je ne comprends pas ...

Hors ligne

#102 30-04-2018 16:28:20

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

Re : crible en python

Ave,

ok Yoshi .
mais je pense qu'il y a un problème à la base d'après ton avant dernier post: au sujet des %3== {0,1, ou2}

pourquoi les énumérer...?

Ce n'étaient que des tests de valeur : rien à voir avec une quelconque modif du prg
Ces tests,  pour des raisons très prosaïques :
- je voulais voir si je pouvais déceler une périodicité et quand elle arrivait,
- et donc de voir comment je pourrais shunter les j%3==0
Mais le pb est que le j s'incrémente de incr
Le j avant l'incrémentation a beau ne pas être multiple de 3 et incr aussi, il arrivera fatalement que le nouveau j (résultat de j+incr) lui le soit.
Si je ne me suis pas mélangé les crayons :
j= 7                 j%3 = 1
incr =11       incr%3 = 2
           et
(j+incr)%3 = 0

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#103 30-04-2018 16:56:25

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

Re : crible en python

yoshi a écrit :

Ave,

ok Yoshi pour ces tests

Mais le pb est que le j s'incrémente de incr
Le j avant l'incrémentation a beau ne pas être multiple de 3 et incr aussi, il arrivera fatalement que le nouveau j (résultat de j+incr) lui le soit.

mais qu'elle importance , puisque tu passes: 1) par  l'étape des j += incr <f donc , tu as tes 15j

étape 2) tu reviens au premier j, tu testes si j dico%30==0 sinon, tu passes au j suivant ...où est l'erreur  ?

par ex j 51 , qui est un 3m on s'en fou, je test dico%30==0 : donc je teste si j1%30==0 ou j11%30 == 0 sinon je passe au j suivant...
dans tous les cas dans cette configue actuelle on fait au maxi 3 tests par j, au lieu de deux et au mimum 1 seul  si j=61 : test j %30==1 ok , donc positonne, criblage, le suivant...

déjà je pense qu'il est plus rapide d'établir les 15j  est de commencer les tests et le criblage au fur et à mesure de la list...

Si je ne me suis pas mélangé les crayons :
j= 7                 j%3 = 1
incr =11       incr%3 = 2
           et
(j+incr)%3 = 0

bien sûr , mais pour chaque Pi , l'ordre changera par obligation ..chaque pi est unique et engendre ordre différent mais cyclique pour chaque Pi...
donc tu ne peux pas espérer sauter j%3 ou 5  =  en passant par un cycle qui va perdre du temps, compliquer la programmation...etc

la seule possibilité c'est de faire le test j == dico%30 ok sinon suivant  ....non ???

Hors ligne

#104 30-04-2018 17:06:38

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

Re : crible en python

la nouvelle modif ,pour 3000000000 est plus longue , je suppose que cela vient des j%5 en plus..

Hors ligne

#105 30-04-2018 18:44:37

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

Re : crible en python

Non,

Pas logique, parce que j'ai viré tous les calculs de d_c...
Revoilà le bloc d'origine mis à part le calcul de f où j'ai laissé pi*29...


    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):  
        r.append(nn % pi)
        pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        j = r[i]
        f=j+pi*29
        incr = pi*2
        d_c = j%10
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if j %2==0:
            j += pi
        while j <=f:
            if j%3!=0 and d_c%5!=0:              
                fam =Dico[j%30]      
                if 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))

Retrouves-tu la vitesse antérieure ?

@+

[EDIT] Alors ça c'est curieux :
Avec
if j%3!=0 and d_c%5!=0:
j'ai un plantage que je n'ai plus avec :
if j%3!=0 and j%5!=0:

[EDIT2]
J'ai trouvé.
J'avais oublié de remettre un d_c = j% ici

 
       if j %2==0:
            j += pi

Si je le remets et que je remplace ensuite
if j%3!=0 and j%5!=0:
par
if j%3!=0 and d_c!=5 :
ça ne plante plus...

Ceci me montre qu'écrire :

 if j %2==0:
            j += pi
        while j <=f:
            if j%3!=0 and j%5!=0:

     
est correct...

Mais une question se pose alors : à quoi servent les instructions d_c=j%10 dans ce cas ?
Ce qui ramène à la surface la question :
pourquoi est-ce moins rapide de virer toutes les affectations d_c=j%10 et de tester avec j%5!=0...?
Je me répète : pas logique...

Je vais creuser...

Dernière modification par yoshi (30-04-2018 18:51:10)


Arx Tarpeia Capitoli proxima...

Hors ligne

#106 30-04-2018 19:31:00

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

Re : crible en python

RE,

Comparaison de vitesses entre :

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,nn = n//30,n*2
    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 = []
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
           
    print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):  
        r.append(nn % pi)
        pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        j = r[i]
        f=j+pi*30
        incr = pi*2
        d_c = j%10
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if j %2==0:
            j += pi
            d_c=j%10
        while j <=f:
            if j%3!=0 and d_c!=5:              
                fam =Dico[j%30]      
                if 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):
        pi=p[i]
        for j in range(8):
            index = (pfam[i][j] - p8[j])//30          
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
    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")

et

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,nn = n//30,n*2
    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 = []
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
           
    print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):  
        r.append(nn % pi)
        pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        j = r[i]
        f=j+pi*29
        incr = pi*2
       
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if j %2==0:
            j += pi            
        while j <=f:
            if j%3!=0 and j%5!=0:              
                fam =Dico[j%30]      
                if pfam[i][fam] == 0:
                    pfam[i][fam] = j
            j += incr
           
 
    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, pi in enumerate(in range(lenpfam):
        pi=p[i]
        for j in range(8):
            index = (pfam[i][j] - p8[j])//30          
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
    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")

Sorties

Donnez la valeur de n = 30k : 240000000
Crible mod30 : Initialisation: 5.239299774169922 seconds ---
Crible mod30 : Famille de chaque Pi: 0.5170297622680664 seconds ---
Crible mod30 : Criblage des 8 familles: 23.28733205795288 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 15.417881727218628 seconds ---
On a 12194880 nombres premiers

=====
Donnez la valeur de n = 30k : 240000000
Crible mod30 : Initialisation: 5.091291189193726 seconds ---
Crible mod30 : Famille de chaque Pi: 0.47702741622924805 seconds ---
Crible mod30 : Criblage des 8 familles: 23.25332999229431 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 14.977856636047363 seconds ---
On a 12194880 nombres premiers

Un poil plus rapide...

Voilà qui me rassure.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#107 30-04-2018 20:07:52

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

Re : crible en python

Pourtant tout à l'heure  j'avai bien le deuxième prog moins rapide qu'avec les D-c ...

environ une 20 de secondes pour 3000000000.
je vais vérifier...
concernant ma question et ma supposition, sur l'ordre des étapes...tu as une réponse..sans s'occuper des d_c et j%3 ==0...???

Hors ligne

#108 30-04-2018 20:27:24

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

Re : crible en python

je viens de faire la même connerie mais à l'envers...j'ai laissé le   si d_c %2==0 et d_c =  j%10

Hors ligne

#109 30-04-2018 20:45:40

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

Re : crible en python

LEG a écrit :

je viens de faire la même connerie mais à l'envers...j'ai laissé le   si d_c %2==0 et d_c =  j%10

avec les d_c = j%10

Donnez la valeur de n = 30k : 300000000
CribleG5 mod30 : Initialisation: 3.6504063606262207 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.14040017127990723 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 14.648425817489624 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 6.411611318588257 seconds ---
On a 15072378 nombres premiers
Appuyez sur une touche pour continuer...

sans les D_c

Donnez la valeur de n = 30k : 300000000
CribleG5 mod30 : Initialisation: 3.744006395339966 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.15600061416625977 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 14.570425510406494 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 6.474011421203613 seconds ---
On a 15072378 nombres premiers
Appuyez sur une touche pour continuer...

je pense que tu es pire que moi , tu lâches rien.....

Bonne nuit ...@+++

Dernière modification par LEG (01-05-2018 08:33:49)

Hors ligne

#110 01-05-2018 11:10:46

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

Re : crible en python

LEG a écrit :

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+

Hors ligne

#111 01-05-2018 11:32:32

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

Re : crible en python

Bonjour,

Non, je ne lâche prise qui si je suis totalement persuadé que je ne peux vraiment plus rien faire...
Et là, pas encore.
D'abord quelques modifs "cosmétiques" :
- j'ai déplacé une ou deux bricoles en Initialisation pour être plus logique,
- j'ai supprimé le bloc affichage qui ne servait à rien
- j'ai supprimé le tri de la liste premiers qui ne servait à rien : pourquoi essayer de trier plusieurs millions d'éléments qui valent True ?
- la fonction Criblemod30(n) ne retourne plus la liste premiers : ça ne servait à rien. Je retourne son nombre d'éléments...
- eratostene retourne directement premiers[3:]. Pourquoi retourner la totalité, la récupérer et ne prendre qu'à partir de 7 ?
  Autant retourner directement premiers[3:]...


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[3:]

def crible_mod30(n):
    # INITIALISATION
    start_time = time.time()
    nbcell,nn = n//30,n*2
    nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
    p = eratostene(n)
    r = [nn%pi for pi in p]
    p8 = [1, 7, 11, 13, 17, 19, 23, 29]
    pfam = []
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
           
    print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):  
        pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        j = r[i]
        f=j+pi*29
        incr = pi*2        
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if j %2==0:
            j += pi          
        while j <=f:
            if j%3!=0 and j%5!=0:              
                fam =Dico[j%30]      
                if pfam[i][fam] == 0:
                    pfam[i][fam] = j
            j += incr          
 
    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):
        pi=p[i]
        for j in range(8):
            index = (pfam[i][j] - p8[j])//30          
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
    print("Crible mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

    # 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))
    nb=len(premiers)
    return nb
   
n = int(input("Donnez la valeur de n = 30k : "))
print("On a "+str(crible_mod30(n))+" nombres premiers"
os.system("pause")
 

Donnez la valeur de n = 30k : 240000000
Crible mod30 : Initialisation: 5.044288635253906 seconds ---
Crible mod30 : Famille de chaque Pi: 0.48802781105041504 seconds ---
Crible mod30 : Criblage des 8 familles: 21.835248947143555 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 11.73867130279541 seconds ---
On a 12194880 nombres premiers

Maintenant, je rentre dans le dur...
En examinant la liste r (normal, puisque on a écrit j=r['i]), j'ai pu constater quelles contenait des multiples de 2,3 et 5...
Si je n'avais plus que d'autres multiples, ce ne serait pas une garantie de ne plus avoir à tester j%2, j%3 et j%5  à cause du j+= incr.
Pourtant, je pense toujours à 75% qu'on devrait pouvoir contourner la difficulté...

Mais bon, les plus gros consommateurs de temps sont
Criblage des 8 familles et Extraction.
C'est là-dessus que je veux travailler maintenant...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#112 01-05-2018 14:35:56

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

Re : crible en python

Je pense que ta modification et le changement de position dans le calcule des restes = à 2n%pi à ralenti le programme résultat ci-dessous

avec d_c !=5 et j%3!=0
*$Donnez la valeur de n = 30k : 240000000
CribleG5 mod30 : Initialisation: 2.8548049926757812 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.10920023918151855 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 11.715620517730713 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 4.929608583450317 seconds ---
On a 12194880 nombres premiers

- eratostene retourne directement premiers[3:]. Pourquoi retourner la totalité, la récupérer et ne prendre qu'à partir de 7 ?

parce que eratostène extrait les premiers dont le crible à besoin : [tex]\leqslant\sqrt{2n}[/tex] et > 5 car on est dans les 8 familles d'entiers congrus à 1 ou à P[30] avec p premier [7;29] ce qui donne bien les 8 familles c'est à dire les 8 suites arithmétique de raison 30 , de premier terme 1 ou P ci-dessus...

la fonction Criblemod30(n) ne retourne plus la liste premiers : ça ne servait à rien. Je retourne son nombre d'éléments...

tu veux dire les nbcell ==[1], qui sont les nombres premiers q de nà 2n...bien sûr...

dans eratostene effectivement il retourne les premiers > 5 , j'ai laissé car ça ne gênait pas , mais effectivement cela fait une ligne de programme en plus , dans def cribl_mod30

En examinant la liste r (normal, puisque on a écrit j=r['i]), j'ai pu constater quelles contenait des multiples de 2,3 et 5...

ça c'est logique,  mais don on a pas besoins puisque les 8 familles  on pour reste %9 = [1 ,4,7]  pour les 4 familles [1,7,13 19] de raison 30 ; %9 = [2 ,5,8]  pour les 4 familles [11,17,23,29] il suffit de faire la somme des chiffres de j pour savoir à quelle famille ils appartiennent
principe de la preuve par 9..

on sait : que 8j sur 15 appartiennent au 8 familles et que les 7 autres j sont d_c==5 et j%3==0 ...
on ne pourra pas les contourner sans passer par un ordre qui élimine le test et fait passer au j suivant...

par exemple pour chaque pi, on a la liste des 15j < f.

si j ==dico%30 on positionne on crible retour aux j suivant  elif (j est != dico%30) donc on passe au j suivant...point barre.

criblait les 8 familles pose justement ce problème ...("dans l'algorithme nbpremier.win") on l'a programmé, en c++ , mais par famille il y a 15 ans...

crible mod30 je crible par famille: la famille 7
le début ne change en rien ...
mais dans le criblage et les j on a juste besoin de R =2n%pi, la limite j <= f ne changerait pas mais on le fait au fur et à mesure et cela ne peut dépasser f...puisque j= 7%30 == 0 serra dans les 15 j , comme le crible ci-dessus...

si R %2==0 += pi ; il est impair et devient j ; ensuite j += incr wile d_c==7 , il n'y a  que deux cas possible , ok, donc on positionne j  qui donne la position du départ de 7, pour le criblage des nbcell toutes les 7 cellules , puis retour à Pi suivant et R suivant, on réitère.
elif : j += incr  wile d_c==7 donc ok par obligation ...et position, crible, retour pi et R suivant; réitération...!
si R != d_c==7  donc j += incr,  wile d_c==7 ;  j != d_c== 7 , j+=incr  wile d_c==7 ; il n'y a que deux cas possible , donc
: j, d_c == 7 ok par obligation .. on le positionne, pour le départ de pi qui va cribler ; retour , pi et R suivant; réitération...!

ça va beaucoup plus vite.....!

le consommateur de temps c'est la position des 8j et le criblage des 8 familles modulo pi..... car marquer d'un [0] par exemple toutes les (pi = 7) cellules , sur un million de cellules par famille.... c'est longuet...; compter les [1] normalement c'est beaucoup plus rapide...

Dernière modification par LEG (08-09-2018 11:16:50)

Hors ligne

#113 01-05-2018 15:59:19

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

Re : crible en python

Re,

- eratostene retourne directement premiers[3:]. Pourquoi retourner la totalité, la récupérer et ne prendre qu'à partir de 7 ?

Tu te méprends sur le sens de cette question.
Je n'ai noté cette question que pour expliquer la réponse que je donne et la modif faite en conséquence.
Avant, la def eratostene créait la liste premiers qui comprenait les premiers 2, 3 et 5.
Donc on retournait toute la liste, la def crible la récupérait puis la remplaçait par la même liste amputée de 2, 3 et 5.
Maintenant, avec la liste premiers en mémoire, dans la def erato on retourne que ce dont on a besoin premiers[3:]

Je pense que ta modification et le changement de position dans le calcule des restes = à 2n%pi à ralenti le programme résultat ci-dessous

Non, je ne pense pas.
J'ai augmenté le temps de l'initialisation, certes, c'est normal.
Mais le temps de traitement qui suit doit avoir baissé plus que la phase d'initialisation.
Les temps donnés par Python peuvent être trompeurs : sur 3 à 4 essais consécutifs avec le même n, le même programme peuvent donner des temps différents.
Dans la phase de traitement Familles pour chaque pi, il n'y a plus r.append(nn%pi) remplacée dans l'initialisation
r=[nn%pi for pi in p]
Pourquoi ?
Parce que j'ai pensé qu'ajouter un élément à la fois dans le traitement obligeait à faire des allers-et retours à la liste r puisque à chaque tour de boucle, entretemps, le prog a fait autre chose.
Là, avec ma liste en compréhension, je crée r d'un coup...

Tu as encore cette version C ? Je voudrais bien la voir  --> yoshik_at_no-log.org (Remplacer _at_ par @)


@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#114 01-05-2018 16:19:28

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

Re : crible en python

ok pour ton explication sur eratostene mais j'en étais pas sûr j'ai bien compris cette utilité d'éviter de reprendre une liste avec2,3 et 5.

j'ai refais plusieurs fois le test pour moi il est plus rapide que la nouvelle version mais il se pourrait aussi que cela vienne de la dernière partie

 print("Crible mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
    nb=len(premiers)
    return nb

je n'ai pas modifié cette partie ni le calcul de r = 2n%pi que je ferai au fur et à mesure pour voir..

pour la version G4 avec  r=[nn%pi for pi in p] , je ne l'ai pas gardé car elle marchait beaucoup moins vite que G5

version de ton post ci dessus:

def crible_mod30(n):
    # INITIALISATION
    start_time = time.time()
    nbcell,nn = n//30,n*2
    nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
    p = eratostene(n)
    r = [nn%pi for pi in p]
    p8 = [1, 7, 11, 13, 17, 19, 23, 29]
    pfam = []
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
 

actuellement voici G5 sans cette modif ci-dessus:


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[3:]

def cribleG5_mod30(n):
    # INITIALISATION
    start_time = time.time()
    nbcell,nn = n//30,n*2
    nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
    p = eratostene(n)
    lenp = len(p)
    r = []
    p8 = [1, 7, 11, 13, 17, 19, 23, 29]
    pfam = []
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}

    print("CribleG5 mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):
        r.append(nn % pi)
        pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        j = r[i]
        f=j+pi*29
        incr = pi*2
        d_c = j%10
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if d_c %2==0:
            j += pi
            d_c = j%10
        while j <= f:
            if j%3!=0 and d_c!=5:
                fam =Dico[j%30]
                if pfam[i][fam] == 0:
                    pfam[i][fam] = j
            j += incr
            d_c = j%10
            #print(j)
    print("CribleG5 mod30 : Famille de chaque couple R et 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):
        pi=p[i]
        for j in range(8):
            index = (pfam[i][j] - p8[j])//30
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
    print("CribleG5 mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

    # 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("CribleG5 mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
    #print(nombres)
    premiers.sort()
    return premiers

n = int(input("Donnez la valeur de n = 30k : "))
nb = len(cribleG5_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
 

je n'ai pas encore modifier les deux ligne 87 et 88...

Dernière modification par LEG (01-05-2018 16:42:16)

Hors ligne

#115 01-05-2018 16:37:32

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

Re : crible en python

Re,

La seule façon de trancher cette histoire de vitesse serait la chose suivante :
on somme les durées de l'initialisation et de Famille pour chaque pi
- dans mon dernier code
- dans le même code mais où on a rétabli r.append(nn%pi) et remplacé r=[nn%pi for pi in p] par r[]
Puis on compare les deux.

Allez, je le fais
3 essais avec r.append  : 5.52431583404541 s, 5.655323266983032 s et 5.571318864822388 s
3 essais avec r déplacé : 5.529316425323486 s, 5.543317079544067 s et 5.5503175258636475 s

Bon, même si j'ai raison, il n'y a rien de fondamental : l'écart maxi est de 1/10e s !

Avec n = 240000000

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#116 01-05-2018 16:53:02

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

Re : crible en python

donc la différence sur G5 par rapport à la version de ton post ci dessus , sont les lignes35.36.46.57 j'ai garder d_c=j%10 et les deux dernières ligne 87 .88. avant la fin...

3 essais avec G5 :

1)
Donnez la valeur de n = 30k : 240000000
CribleG5 mod30 : Initialisation: 3.400806188583374 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.12480020523071289 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 11.544020175933838 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 4.9296088218688965 seconds ---
On a 12194880 nombres premiers
Appuyez sur une touche pour continuer...
2)
Donnez la valeur de n = 30k : 240000000
CribleG5 mod30 : Initialisation: 2.839205026626587 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.10920023918151855 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 11.48162031173706 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 4.992008686065674 seconds ---
On a 12194880 nombres premiers
Appuyez sur une touche pour continuer...

et 3)
Donnez la valeur de n = 30k : 240000000
CribleG5 mod30 : Initialisation: 2.8548049926757812 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.10920023918151855 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 11.528420209884644 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 4.9296088218688965 seconds ---
On a 12194880 nombres premiers
Appuyez sur une touche pour continuer...

Dernière modification par LEG (01-05-2018 16:58:22)

Hors ligne

#117 01-05-2018 17:12:23

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

Re : crible en python

si je comprend bien ta version : tu calcul les r 2n%pi dans l'initialisation et ensuite tu les rappelles pour famille de pi . calcul des j, positionner, cribler et tu retournes chercher le pi suivant

alors que dans G5,  les r, on les calcule au fur et à mesure dans famille de pi pour calculer les j , les positionner , cribler et pi suivant on réitère...
non...?

Hors ligne

#118 01-05-2018 18:56:33

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

Re : crible en python

B'soir,

Dans ma dernière version :
* j'ai viré toute référence à d_c, je ne m'occupe plus que des j
* oui, au lieu de construire r au coup par coup avec append(), j'ai supprimé cette ligne, et j'ai modifié le r =[] en r=[nn%pi for pi in p].
   Je me suis dit que, quitte à déclarer la liste r pour ne la construire que plus tard au coup par coup, autant la construire d'entrée de jeu, puisqu'elle n'est plus modifiée ensuite.

Les temps fournis en post #116 ont été chaque fois obtenus en additionnant les temps des 2 premières lignes de la sortie de chacun de mes 6 essais...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#119 02-05-2018 04:40:20

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

Re : crible en python

yoshi a écrit :

B'soir,

Dans ma dernière version :

* oui, au lieu de construire r au coup par coup avec append(), j'ai supprimé cette ligne, et j'ai modifié le r =[] en r=[nn%pi for pi in p].
   Je me suis dit que, quitte à déclarer la liste r pour ne la construire que plus tard au coup par coup, autant la construire d'entrée de jeu, puisqu'elle n'est plus modifiée ensuite.

@+

Oui tu as raison , d'autant qu'il faut retourner chercher le pi suivant , donc avec R  ie: le couple  (pi et R ) je modifie..
@+

Dernière modification par LEG (06-05-2018 17:37:39)

Hors ligne

#120 02-05-2018 06:13:26

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

Re : crible en python

avec ces lignes à la fin du programme je peux le lancer la fenêtre cmd ok


   premiers.sort()
    return premiers

n = int(input("Donnez la valeur de n = 30k : "))
nb = len(cribleG5_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
 

par contre si je laisse tes dernières lignes :


   nb=len(premiers)
    return nb
   
n = int(input("Donnez la valeur de n = 30k : "))
print("On a "+str(crible_mod30(n))+" nombres premiers"
os.system("pause")
 

la fenêtre cmd se ferme de suite quand je lance n=150

dans l' IDLE cela me met [invalid syntaxe ] et me met en rouge os

os.system("pause")
  ????

ça y ai ...j'ai oublié le ) à la fin de la ligne print+" nombres premiers"

il est xénophobe pycharm .....Lolllll

Dernière modification par LEG (02-05-2018 06:42:02)

Hors ligne

#121 02-05-2018 06:40:28

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

Re : crible en python

Bonjour,


Chez toi, il doit manquer tout au début du programme : import os.
Si non, alors tu as dû faire une petite modif mal corrigée quelque part...

Je te remets donc la dernière version qui ne génère aucun problème chez moi, que ce soit à n=150, n=240, n=150000 ou n =3000000.
Copie/colle dans une page vierge.


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[3:]

def crible_mod30(n):
    # INITIALISATION
    start_time = time.time()
    nbcell,nn = n//30,n*2
    nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
    p = eratostene(n)
    r=[nn%pi for pi in p]
    p8 = [1, 7, 11, 13, 17, 19, 23, 29]
    pfam = []
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
           
    print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):  
        pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
       
        j = r[i]
        f=j+pi*29
        incr = pi*2        
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if j %2==0:
            j += pi          
        while j <=f:
            if j%3!=0 and j%5!=0:              
                fam =Dico[j%30]      
                if pfam[i][fam] == 0:
                    pfam[i][fam] = j
            j += incr          
 
    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):
        pi=p[i]
        for j in range(8):
            index = (pfam[i][j] - p8[j])//30          
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
    print("Crible mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

    # 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))
    nb=len(premiers)
    return nb
   
n = int(input("Donnez la valeur de n = 30k : "))
print("On a "+str(crible_mod30(n))+" nombres premiers")
os.system("pause")
 

Preuve :

Python 3.5.2 (v3.5.2:4def2a2901a5, Jun 25 2016, 22:18:55) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>>
===== RESTART: C:\Python35\Progs persos\v3.x\Crible_revu_premiers LEG_indente_4spc_quater.py =====
Donnez la valeur de n = 30k : 150
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 27 nombres premiers
>>>
===== RESTART: C:\Python35\Progs persos\v3.x\Crible_revu_premiers LEG_indente_4spc_quater.py =====
Donnez la valeur de n = 30k : 150000
Crible mod30 : Initialisation: 0.006000518798828125 seconds ---
Crible mod30 : Famille de chaque Pi: 0.002000093460083008 seconds ---
Crible mod30 : Criblage des 8 familles: 0.019001245498657227 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 0.012000799179077148 seconds ---
On a 12149 nombres premiers
>>>
===== RESTART: C:\Python35\Progs persos\v3.x\Crible_revu_premiers LEG_indente_4spc_quater.py =====
Donnez la valeur de n = 30k : 240
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 40 nombres premiers
>>>
===== RESTART: C:\Python35\Progs persos\v3.x\Crible_revu_premiers LEG_indente_4spc_quater.py =====
Donnez la valeur de n = 30k : 3000000
Crible mod30 : Initialisation: 0.07900452613830566 seconds ---
Crible mod30 : Famille de chaque Pi: 0.009000539779663086 seconds ---
Crible mod30 : Criblage des 8 familles: 0.2040114402770996 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 0.1630094051361084 seconds ---
On a 196033 nombres premiers
>>>

Avec l'IDLE, j'ai même la fenêtre cmd qui s'ouvre à la fin, demandant d'appuyer sur une touche.
Si ton pb persiste, envoie-moi le fichier.py qui te fait des blagues afin que je puisse le rester chez moi.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#122 02-05-2018 06:42:50

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

Re : crible en python

ça y ai ...j'ai oublié le ) à la fin de la ligne print+" nombres premiers"

il est xénophobe pycharm .....Lolllll

j'ai bien ta dernière version ci-dessus et rassure toi elle fonctionne parfaitement, c'est tout simplement que j'avais copié et colle les dernières lignes de ton post 112 d'hier, où il manque le ) ...mais je suppose que c'est pour me faire comprendre les erreurs afin que je cherche...

je fais quelques tests > 3 mds pour voir
puis je vais "éssayer" de modifier pour ne prendre que la famille p8 = 1 et dico[1:0] , hier je n'ai pas réussi mais je pense que cela vient de famille = fam que je paramètre mal... ainsi que famille de pi

je met aussi la limite
wile:
j != dico[1]%30.

de sorte qu'il crible des que cette condition et bonne , passe à Pi suivant...

Dernière modification par LEG (08-09-2018 11:24:34)

Hors ligne

#123 02-05-2018 08:28:16

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

Re : crible en python

Et ben : je viens de faire un condensé de G4; G5 ta dernière version ci-dessus et G6

G4 : 2ème essais.
Donnez la valeur de n = 30k : 3000000000
CribleG4 mod30 : Initialisation: 35.97366285324097 seconds ---
CribleG4 mod30 : Famille de chaque Pi: 1.4040026664733887 seconds ---
CribleG4 mod30 : Criblage des 8 familles: 185.96792650222778 seconds ---
CribleG4 mod30 : Extraction des premiers n à 2*n : 62.649710178375244 seconds ---
On a 135095831 nombres premiers
Appuyez sur une touche pour continuer...

G5 :....
Donnez la valeur de n = 30k : 3000000000
CribleG5_mod30 : Initialisation: 38.485267639160156 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 3.8532068729400635 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 171.9435019493103 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 91.44736051559448 seconds ---
On a 135095831 nombres premiers
Appuyez sur une touche pour continuer...

G6:....
Donnez la valeur de n = 30k : 3000000000
CribleG6 mod30 : Initialisation: 36.06726312637329 seconds ---
CribleG6 mod30 : Famille de chaque couple R et Pi: 1.419602632522583 seconds ---
CribleG6 mod30 : Criblage des 8 familles: 167.18549370765686 seconds ---
CribleG6 mod30 : Extraction des premiers n à 2*n : 62.758910179138184 seconds ---
On a 135095831 nombres premiers
Appuyez sur une touche pour continuer...

voila ta dernière version dont j'ai changer les paramètres en gardant les D_c ,  la ligne 51 ; la ligne 55 et le dernier bloc de la ligne  85 à91
tu peux d'ailleurs comparer avec l'ancienne G5, que je t'ai posté hier à 17h


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[3:]

def cribleG6_mod30(n):
    # INITIALISATION
    start_time = time.time()
    nbcell,nn = n//30,n*2
    nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
    p = eratostene(n)
    r = [nn%pi for pi in p]
    p8 = [1, 7, 11, 13, 17, 19, 23, 29]
    pfam = []
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}

    print("CribleG6 mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):
        pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        j = r[i]
        f=j+pi*29
        incr = pi*2
        d_c = j%10
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if d_c %2==0:
            j += pi
            d_c = j%10
        while j <= f:
            if j%3!=0 and d_c!=5:
                fam =Dico[j%30]
                if pfam[i][fam] == 0:
                    pfam[i][fam] = j
            j += incr
            d_c = j%10
            #print(j)
    print("CribleG6 mod30 : Famille de chaque couple R et 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):
        pi=p[i]
        for j in range(8):
            index = (pfam[i][j] - p8[j])//30
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
    print("CribleG6 mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

    # 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("CribleG6 mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
    #print(nombres)
    premiers.sort()
    return premiers

n = int(input("Donnez la valeur de n = 30k : "))
nb = len(cribleG6_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
 

Hors ligne

#124 02-05-2018 09:47:35

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

Re : crible en python

c'est le noir complet  , voila ce qu'il me met, aptres avoir modifier pour ne travailler que dans la famille 1%30:


Donnez la valeur de n = 30k : 150
CribleG1_mod30 : Initialisation: 0.0 seconds ---
Traceback (most recent call last):

  File "E:\executable algo P(30)\cribleG1_modulo30 à modifier.py", line 88, in <module>
    nb = len(cribleG1_mod30(n)) (# no comprend...???]

  File "E:\executable algo P(30)\cribleG1_modulo30 à modifier.py", line 56, in cribleG1_mod30
    if pfam[i][fam] == 1: (# javais laissé le 0, mais pareil..???)
IndexError: list index out of range
 

voici le code:


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[3:]

def cribleG1_mod30(n):
    # INITIALISATION
    start_time = time.time()
    nbcell,nn = n//30,n*2
    nombres = [[1 for _ in range(nbcell)] for _ in range(1)]
    p = eratostene(n)
    r = [nn%pi for pi in p]
    p8 = 1
    pfam = []

    print("CribleG1_mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

    # FAMILLES POUR CHAQUE Pi
    start_time = time.time()
    for i,pi in enumerate(p):
        pfam.append([0,])
        j = r[i]
        f=j+pi*29
        incr = pi*2
        d_c = j%10
        #  si la terminaison du reste est paire on ajoute directement pi et on verifie
        if d_c %2==0:
            j += pi
            d_c = j%10
        while j <=f:
            if j%3!=0 and d_c!=5:
                fam =p8%30
                if pfam[i][fam] == 1:
                    pfam[i][fam] = j
            j += incr
            d_c = j%10
            print(j)
    print("CribleG1 mod30 : Famille de chaque couple R et Pi: %s seconds ---" % (time.time() - start_time))

    #ON CRIBLE LES la COLONNES 1%30 AVEC CHAQUE FAMILLE DE pi
    start_time = time.time()
    lenpfam = len(pfam)
    for i in range(lenpfam):
        pi=p[i]
        for j in range(1):
            index = (pfam[i][j] - p8[j])//30
            while index < nbcell:
                nombres[j][index] = 0
                index += pi
    print("CribleG1 mod30 : Criblage de la familles: %s seconds ---" % (time.time() - start_time))

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time.time()
    premiers = []
    for i in range(1):
        for j in range(nbcell-1, -1, -1):
            if nombres[i][j] == 1:
                premiers.append(nombres[i][j] == 1)
    print("CribleG1 mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
    print(nombres)
    premiers.sort()
    return premiers

n = int(input("Donnez la valeur de n = 30k : "))
nb = len(cribleG1_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
 

je sens que peut être je n'en suis pas loin....mais dans le noir, loin : peu être très loin....

Hors ligne

#125 02-05-2018 12:16:56

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

Re : crible en python

Re,

S'il te plaît, la balise code fournit un code bien plus lisible si tu la modifies en [code=Python)...

File "E:\executable algo P(30)\cribleG1_modulo30 à modifier.py", line 88, in <module>
    nb = len(cribleG1_mod30(n)) (# no comprend...???]

  File "E:\executable algo P(30)\cribleG1_modulo30 à modifier.py", line 56, in cribleG1_mod30
    if pfam[ i][fam] == 1: (# javais laissé le 0, mais pareil..???)
IndexError: list index out of range

Ton message est pourtant explicite :
list index out of range signifie simplement que l'un des index avec lequel tu tentes d'accéder à la liste pfam, soit fam, soit i, est trop grand.

Tu peux reproduire cette erreur et c'est plus simple à faire je pense  dans l'IDLE comme ça :

Python 3.5.2 (v3.5.2:4def2a2901a5, Jun 25 2016, 22:18:55) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> L=[1,2,3]
>>> print (L[5])
Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    print (L[5])
IndexError: list index out of range

>>>

Immédiatement en dessous de la déclaration def crible et au-dessus de initialisation...
Tu vas écrire :
global i,fam,pfam
Cela va rendre i, fal, pfam globales et plus locales : elles seront visibles en dehors de la def...

Puis tu lance ton prog dans l'IDLE avec n= 150, par exemple...
Je viens de le faire...
Devant le prompt >>> tu tapes, i,fam,pfam (Entree)
Affichage :
(0, 1, [[0]])
Et là explication saute aux yeux, ce n'est ni vraiment la faute de i ou de fam mais celle de pfam !!!
En effet, tu initialisais pfam ainsi : pfam=[[0,0,0,0,0,0,0,0]]
Or, là, pfam vaut [[0]], et donc pfam[0] renvoie [0]
Mais pfam[0][1] tente d'accéder au 2e élément de pfam[0] lequel n'existe pas, donc un message d'erreur t'informe que tu tentes d'accéder à un élément de la liste pfam dont l'index est : out of range, hors limite !

Boum !
Il y a encore un autre problème
Tu initialises p8 comme ça : p8=1 Donc là, p8 est un nombre.
Et ici, tu demandes :

index = (pfam[i][j] - p8[j])//30

Et p8[j] renvoie l'erreur disant que p8 n'est pas indexable, qu'on ne peut pas y accéder avec un index vu que c'est un nombre...

@+

Dernière modification par yoshi (02-05-2018 12:31:08)


Arx Tarpeia Capitoli proxima...

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)?
trente quatre plus cinquante trois
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