De LEG

LEG · Programmation

ce que je bricole..:et je viens de suivre tes explications tout marche sauf que je n'ai pas les bons nombres pour la famille (1) modulo 30 uniquement .

avant p8 [1.7.11.13.17.19.23.29] représentait les 8 famille à cribler comme dans ton crible

et pour n = 150
cela nous donne pour la famille (1) modulo 30 : le résultat suivant avec G5 ou ton crible .. en rouge la famille (1) modulo 30 ensuite tu as la deuxième (7) modulo 30...etc

Donnez la valeur de n = 30k : 150
CribleG5 mod30 : Initialisation: 0.0 seconds ---
CribleG5 mod30 : Famille de chaque couple R et Pi: 0.0 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 0.0 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---
[[0, 1, 1, 0, 1], [1, 1, 1, 0, 1], [0, 0, 1, 1, 0], [0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 0], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1]]
On a 27 nombres premiers
Appuyez sur une touche pour continuer...

je veux cribler que la famille 1 modulo 30 pour n 150 voici le résultat

Donnez la valeur de n = 30k : 150
CribleG1_mod30 : Initialisation: 0.015600204467773438 seconds ---
CribleG1 mod30 : Famille de chaque couple R et Pi: 0.0 seconds ---
CribleG1 mod30 : Criblage des 8 familles: 0.0 seconds ---
CribleG1 mod30 : Extraction des premiers n à 2*n : 0.0 seconds ---

[[1, 1, 1, 1, 0]]
On a 4 nombres premiers

tu vois , ce ne sont pas les bon et là je n'arrive pas à trouver le bon paramètre...pour avoir
[[0, 1, 1, 0, 1]

le principe du crible est le même donc quelque soit la famille unique que je prend je devrais avoir les bonne valeur...

Sauf si je fais des "conn..."

LEG · Programmation

pour fam, j'ai bien remis comme tu viens de le dire [0,0,0,0,0,0,0,0] effectivement cela m'imprime bien les 15j pour les 4 pi avec n=150
je pensais comme il ne reste qu'une famille p8 = 1%30 je pensais que pour fam [0]

yoshi a écrit :

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

idem ci dessus, il ne reste qu'une famille donc j'ai mis p8 = 1,

je viens de mettre p8 = 1%30
et j'ai le même message, d'erreur ...

Et ici, je demandes quoi ??? : si il ne reste que la famille 1%30 ....? et dans p8 = ?

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...
@+

LEG · Programmation

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

LEG · Programmation

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

importos
importmath
importtime

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

LEG · Programmation

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

LEG · Programmation

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

LEG · Programmation

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..
@+

LEG · Programmation

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

LEG · Programmation

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

LEG · Programmation

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

LEG · Programmation

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

LEG · Programmation

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+

LEG · Programmation

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 ...@+++

LEG · Programmation

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

LEG · Programmation

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

LEG · Programmation

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

LEG · Programmation

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

LEG · Programmation

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

LEG · Café mathématique

Bonjour, pourtant la définition d'un nombre premier et très limpide , que l'ancienne définition : tout nombre premier est un nombre qui se divise uniquement par 1 et lui même donc tout nombre composé est un nombre qui se multiplie par 1 est lui même 7*7=49 c'est bien un produit donc 1*1 = 1 c'est bien un produit nombre composé...Alors 1 est un produit et un nombre premier. Va à la recherche des nombres premiers < n , en criblant avec les nombre premiers inférieurs à la racine carrée de n , je ne pense pas que l'on va en trouver beaucoup , on pourra même dire , qu'ils sont en nombres finis....il y en à 1....LoLLLLL
Cordialement.

LEG · Programmation

C'est ce que fait le programme dans l'ordre des étapes...?

Don bien sûr... On voit bien que pour chaque Pi l'ordre de départ change cela ne donnerai rien de mieux si on devait établir pour chaque Pi la liste des 0.1.2, à part une perte de temps et d'alourdir la mémoire...

Par contre établir pour chaque Pi , son R et la suite des j dans la limite de R + pi*29 , pour ensuite faire le test dico%30 ("si ok sinon, on passe à j suivant") on le positionne dans sa famille et on crible, puis on réitère avec le j suivant jusqu'à la fin des p8... Ensuite on passe au Pi suivant...

de même qu'il n'est peut être pas utile je pense, d'établir les liste des R tel que :

for i,pi in enumerate(p):    

        r.append(nn % pi)

pour aller les chercher ensuite , afin d'établir la liste des j impairs... on peut le faire Pour chaque Pi , comme tu l'as justement fait remarquer et modifier...("post précédent...")

Regarde la dernière ligne de Pi = 11 et j = 337 c'est un doublon de la famille 7 modulo 30...car tu cribleras à partir de j = 7 et Pi =11 dans cette famille donc tu passera par 337 ...7 + (11*30) (car, dans chaque famille on crible modulo Pi *30 jusqu'à la lim n fixée comme Eratosthène) il n'y a toujours que 15 J = Ri impair....voila pour quoi je rentre f = Pi*29 .

Tu vas ma dire que c'est pas très grave et la perte de temps est très infime même pour 4mds soit environ 8000 Pi, donc autant de Restes ce qui donnerait 8000 j en plus à traiter....pour rien... Alors que l'on a 8000 * 5 j%3 == 0 = 40000 divisions et pour tous les j; 120000....
Que l'on pourrait peut être éviter si on place le test p8%30 == 0 avant j%3==0.

Car si p8%30 == 0 et ok, on ne fait même pas les deux autres tests , on positionne j dans sa famille et on crible, retour J suivant...

Je comprend pourquoi mon petit fils s'est planté, je pensais qu'il avait compris l'ordre des étapes avec mes explications et le fichier excel, où je lui montrai ce que je faisais....étape par étape...Alors il est vrai que dans mon fichier text, je l'ai mal expliqué car cela me paraissait évident..
limit n , On a les Pi , Pour chaque Pi: calcul de R , liste des j et sa limite F = Pi * 29 ; on commence les teste Dico%30 à partir de J et non de R pair on saute les D_c==5, position, criblage, retour j suivant ... wile P8 fini. Puis réitération avec le Pi suivant...

LEG · Programmation

Bonjour @Yoshi

il y a une question qui me chiffonne , dans ton dernier post relatif au j%3 = 0 ,1 ou 2
je te cite:

Si tu as j%3=2 et incr %3 =1, lorsque tu vas faire j+=incr, le nouveau j obtenu sera bien tel j%3=0 !
Et ça se produit une fois sur 3.
If faut que je détermine exactement quand : apparemment mes premiers tests indiquent une cyclicité dans l'ordre : 2,0,1...
Mais ce n'est pas clair...

Donc tu veux dire que le programme n'établit pas d'abord les 15 j en partant de R +pi et += incr pour R pair, ou R += incr pour R impair dans la limite de R += Pi*29....puis ensuite il va tester les J = Ri sous la condition :

1) R = D_c pair 0k il incrémente j += pi ("# ligne 53 54 ) et passe au suivant donc les j impair jusqu'à j < f on est d'accord..

2) 2 conditions:
a) D_c == 5 , il passe au suivant fam -1, ou saute au suivant...
b) D_c == [1,3,7,9] il teste dans l'ordre : ex D_c ==3 si j % 13 == 0 puis si j%23 == 0 , else il passe au suivant. (# ligne 59 à 63)

pourquoi il ferait j%3 ==0 dans ce cas de figure ??? puisqu'il a mis au par avant les 15 j < f en mémoire et ensuite il va faire les tests pour placer les j dans leur famille fam Dico j%30 et il va cribler par contre à chaque fois qu'il a placé j == Dico j%30 avant de retourner au suivant...de la liste des 15 j.... quelque soit le cas de figure il ferra toujours ça....quelque soit la limite nbcell == n//30 *[1]

je comprend pourquoi dans mes essais cela me changeait et me décalait les 15 j < f...

LEG · Programmation

re

yoshi a écrit :

Bonjour,
dans ce schéma en principe on a pas besoin de if j%3==0 puisque on est toujours obligé de commencer par vérifier en fonction de la décimale D_c [1,3,7,9] Mais j'ai essayé de modifier la ligne 57; if j%3==0 or d_c==5: en ne gardant que d_c==5: ça ne marche pas ...

C'est ce que je comptais te dire ce matin ...
Donc, on ne peut pas, en l'état, faire l'économie du test if j%3==0 or d_c==5.

        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

Je rentre ta modif.
j'ai passé 4h à essayer d'éviter le test if j%3==0. pour rien...
de plus il faut savoir que dans le crible il est impossible de trouver un cycle j%3 == 0 , car pour chaque couple R + Pi la position des multiple de 3 et des D_C == 5 change; sauf si si tu prends par exemple n =210 puis n*210 tu auras toujours la même position de j%3==0 et D_c ==5 mais uniquement pour Pi = 7 ; aucun intérêt car pour les autres Pi ça changera...

ce qui coûte du temps ce n'est pas D_c==5 puisque l'on incr j+2*pi, mais c'est les division de d_c=[1,3,7,9] vérifier si j%3==0

je pensais qu'avec le bloc d'instruction ci dessus on pouvait se passer de j%3 car pour if D_c = '5' on a fam = -1 donc on passe au suivant on incr..

else:

si D_c = ['1','3','7','9'] on vérifie bien

fam =Dico[j%30]      

                if pfam[i][fam] == 0:

                    pfam[i][fam] = j #['si la condition n'est pas remplie donc fausse, on devrait avoir')

fals:

fam = -1  ou fam = incr ou j += incr

puisque cela est possible avec d_c=='5' on vérifie bien la décimale sans division....! non?

peut être qu'il faut le faire pour chaque;

else:

 D_c =='1'  :  #on vérifie 1 et 11 on passe au suiva

  if j%30==1 or j%30==11 

  fam = 0

  fals:  # else = fals

  fam = incr ou  j += incr  ou fam = -1  ...? #puis on passe au suivant

 else :

    D_c =='3'  :  #on vérifie 13 et 23 on passe au suiva

      if j%30==13 or j%30==23 

      fam = 3

  fals: ''ou condition fausse else = fals ..''

      fam = incr ou  j += incr  ou fam = -1 ...? #puis on passe au suivant

...etc ..etc pour 7 et 9
@+

LEG · Programmation

tu m'as donné une idée , mais c'est peut être ce que tu as fait dans G5.
je prend ce bloc

ce bloc calcule les R .append(nn % pi) et les j = R'i' jusqu'à la limite wile j < f, donc < à R +pi*30. prenons le premier pi =7 ; 11; 13; 17; 19...etc pi

pour le premier couple, où n = 240 on a: R = 4 Pi = 7 par exemple , ce qui donne limite = j + 7*29 = 214
on calcule les j dans la limite < 214

j 2+7 ; on incr+2*pi jusqu'à 221 ce qui met en mémoire 16 valeurs:

on sait que D_c == 5 ne se teste pas , on incr et on passe au suivant:

on teste , on positionne grâce au quotient et on crible = marque les nbcell['1] en [0], le quotient donne la position dans [dico....]

pour 11 c'est ok on le position n°0 dans dico 11:2 et on crible..on revient 25 on saute, 39 {19 et 29%30} pas bon on saute 53 ok posit n°1 dico 23:6 cribl retou ; au suiv; 67 ok position n°2 dans dico 7:1 on crible ; retour 81 on saute car 1 et 11%30 pas bon, 95 on saute..109 ok position n°3 dico 19:5 on crible ; retour 123 , 3 et 13%30 pas bon ; suiv 137 ok position n°4 dico 17:4 on crible ; retour 151 ok position n° 5 dico1:0 on cribl ; retou 165 on saute suiv; 179 ok posit n° 5 dico 29:7 cribl ; retou 193 ok posit n° 6 dico 13:3 cribl ; retou 207 , 7 et 17%30 pas bon suiv 221 > 214 fin pour ce Pi.

couple R = 11, Pi =7

#masqué , position n°0 dico 11:2 cribl ['1] = [0] , retour suivant

saute

!= 9 et 19%30

ok

ok 

!= 1 et 11%30

saute 

ok

 != 13 et 23%30

 ok

 ok 

 saute

 ok

 ok les 8 familles terminées pour ce couple R et Pi au suivant.

207

221

on prend le couple R et Pi suivant = 7 ; Pi =11 et on réïtère limite j +11*29 = 7+319 = 326 et le dernier 337 > 326 ne serra pas testé...

7  #qui est masqué, est testé, puis posit N°0 dico 7:1  les nbcell [1] deviennent [0]

29 posit n°0 dico 29:7

51

73 posi n°2 dico 13:3

95

117

139 posi n°4 dico 19:5

161 posi n°5 dico 11:2

183

205

227 posi n°7 dico 17:4

249

271 posi n°9 dico 1:0

293 posi n°9 dico 23:6

315

337 >  326

pi suivant = 13 ...etc ..etc

dans ce schéma en principe on a pas besoin de if j%3==0 puisque on est toujours obligé de commencer par vérifier en fonction de la décimale D_c [1,3,7,9] Mais j'ai essayé de modifier la ligne 57; if j%3==0 or d_c==5: en ne gardant que d_c==5: ça ne marche pas ...

File "E:\Documents\conjecture de Goldbach\cribleG5_modulo30.py", line 60, in cribleG5_mod30

    fam =Dico[j%30] 

KeyError: 27

je l'ai ajouté à la ligne 60

else:                

                fam =Dico[j%30]     

                if pfam[i][fam] == 0:

                    pfam[i][fam] = j

et comme les 8 familles ont été criblées à j == 293 ; on passera au pi suivant, s'en s'occuper de j= 315 , 337...

voila le fonctionnement du crible et cela correspond en principe à ta dernière modif ...

bonne soirée . au cas où, tu as mon adresse mail.....

# 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

LEG · Programmation

Je prends un autre exemple simple.
La multiplication dite "arabe"...
Il n'y a guère qu'une seule méthode à la main, particulièrement simple : on y utilise une grille,...etc

là tu me surprends , car si tu m'avais posé la question, sans hésiter je t'aurait répondu que la seule méthode à la main était de multiplier avec les doigts......bon je me cache comme les autruches...
@+
tu ne veux pas aller au restau.... ??? pour que je t'encourage à te pencher sur la méthode par famille uniquement...????

Je te souhaite un très bon week end ainsi qu'à ta petite Famille...

LEG · Programmation

j'ai bien vue tes modification en comparant G4 et G5 mais sans comprendre ce que cela impliquait , avec tes explications effectivement il y a une sacrée différence entre aller chercher un p['i] à chaque fois et n'y aller le chercher que lorsque les 8 familles sont criblées avec P['i], donc une fois sur 8...
de même pour les familles de p[i'] où l'ancien programme calculait les j avec son p['i'] jusqu'à n ce qui est stupide au lieu de j = f = p['i]*29 ; car là tu multiplies le temps par 10 pour famille des p['i].c'est en imprimant les j que j'ai vu cette erreur..

("que l'on prenne 29 ou 30 cela ne va pas changer grand chose; si ce n'est que le 16ème j = r['i] est un doublon puisque l'on va cribler à partir de la position de j dans sa famille")

pareil pour Eratosthène ou il criblait jusqu'à n, alors que l'on a besoins de p, que jusqu'à la sqrt de n...

mon petit fils me disait même si je ne comprend pas le principe de fonctionnement c'est pas grave.....???? comment peux tu faire un programme qui fonctionne très très bien si tu n'en connais pas les astuces...enfin ...je savais qu'il me fallait le modifier ensuite...

pour aller dans ton sens , le programme des nombres premiers de 7 à n qui a été fait par un pro à l'époque, en C++ , prime.exe fichier csv;

il va 5 fois moins vite que G5 et il est limité à 1500 méga...tu me diras il y a 15 ans c'était peut être moins rapide .... alors qu'il n'y a pas de calcule du modulo ni de multiplication

Alors qu' à la même époque, un étudiant à l'ESSi de Sophia Antipolis 06 , me l'a refait en C++, par Famille , limite 450 000 000 000 et temps de calcule pour 3 000 000 000, cinq fois plus vite que G5, mais par Famille; ce qui ferait pour l'exemple ci dessous 64secondes.. et il écrit sous windows pas sous dos...je ne sais pas si cela change...

 temps 8 secondes 

Allocation du Tableau en cours...

>Allocation Terminée!

>Calcul du tableau en cours...

>Calcul du tableau terminé!

>Le dernier nombre est:

2999999647

>trouvé à la position:

18056145

par contre c'est vrai que l'allocation du tableau qui correspond à l'initialisation est très très rapide...

Forum de mathématiques - Bibm@th.net

#576 Re : Programmation » crible en python » 02-05-2018 14:54:22

#577 Re : Programmation » crible en python » 02-05-2018 12:52:45

#578 Re : Programmation » crible en python » 02-05-2018 09:47:35

#579 Re : Programmation » crible en python » 02-05-2018 08:28:16

#580 Re : Programmation » crible en python » 02-05-2018 06:42:50

#581 Re : Programmation » crible en python » 02-05-2018 06:13:26

#582 Re : Programmation » crible en python » 02-05-2018 04:40:20

#583 Re : Programmation » crible en python » 01-05-2018 17:12:23

#584 Re : Programmation » crible en python » 01-05-2018 16:53:02

#585 Re : Programmation » crible en python » 01-05-2018 16:19:28

#586 Re : Programmation » crible en python » 01-05-2018 14:35:56

#587 Re : Programmation » crible en python » 01-05-2018 11:10:46

#588 Re : Programmation » crible en python » 30-04-2018 20:45:40

#589 Re : Programmation » crible en python » 30-04-2018 20:27:24

#590 Re : Programmation » crible en python » 30-04-2018 20:07:52

#591 Re : Programmation » crible en python » 30-04-2018 17:06:38

#592 Re : Programmation » crible en python » 30-04-2018 16:56:25

#593 Re : Programmation » crible en python » 30-04-2018 16:09:59

#594 Re : Café mathématique » Du dogmatisme de nos définitions de la gêne ultérieure occasionnée » 30-04-2018 13:09:41

#595 Re : Programmation » crible en python » 30-04-2018 10:24:39

#596 Re : Programmation » crible en python » 30-04-2018 07:54:55

#597 Re : Programmation » crible en python » 29-04-2018 10:39:26

#598 Re : Programmation » crible en python » 28-04-2018 18:14:56

#599 Re : Programmation » crible en python » 28-04-2018 15:14:39

#600 Re : Programmation » crible en python » 28-04-2018 15:03:50

Pied de page des forums