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

#76 27-04-2018 15:29:12

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

Re : crible en python

pour n=12000 avec mon ancienne indentation, c'est ok résultat:

Donnez la valeur de N = 30k : 12000
Crible mod30 : Famille de chaque Pi: 0.0 seconds ---
Crible mod30 : Criblage des 8 familles: 0.015600204467773438 seconds ---
On a 1230 nombres premiers
Appuyez sur une touche pour continuer...

par contre, ton indentation dans pycharm ,ne s'ouvre pas ...lorsque je lance, la fenêtre cmd se ferme de suite  ????

avec qu'elle application tu lances ton programme....

Hors ligne

#77 27-04-2018 16:10:58

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Salut,

D'abord rectifie la dernière ligne :
os.system(pause) ---> os.system("pause") (guillemets autour de pause)

Ça devrait venir de là !
J'ai gaffé en le rajoutant à la fin (je ne l'ai pas mis sur dans le code qui est sur ma bécane parce que je n'en ai pas besoin) directement dans mon post.
L'erreur de syntaxe suffit peut-être pour tout bloquer avec Pycharm. Va falloir que je l'installe...
De base, j'utilise l'IDLE (installé automatiquement) de Python. Chez moi, on le trouve ici : C:\Python35\Lib\idlelib\idle.pyw.
Une fois dans Python (ton dossier Python, j'ignore où il est chez toi), tu suis le chemin et tu le trouves : on peut le lancer par double clic dessus...
Moi j'ai un raccourci dans la barre des tâches qui pointe dessus...
Je lance l'IDLE, je peux y faire des tests...
J'ouvre le menu File, je  choisis New File.
Dans cette fenêtre, je colle directement le code que j'ai copié sur Bibmaths (page précédente) sans la dernière ligne, puis
- soit menu Run, puis Run Module
- soit quand on le sait, on appuie sur F5

Avec la dernière ligne, j'ai un message d'erreur qui dit : j'connais pas l'instruction pause (ça a fonctionné jusque là).
os.system("pause") ouvre chez moi, une fenêtre cmd qui attend que je la ferme...
Toi, avec Pycharm, tu travailles totalement en fenêtre cmd qui se ferme, si pas de temporisateur.
Et comme l'exécution dure 2/1000e s, tu ne rends compte de rien.
Mais Pycharm devrait détecter l'erreur de syntaxe. Peut-être d'ailleurs est-ce le cas, mais la fenêtre se ferme avant que tu aies le temps de voir...
Recommence en rajoutant les guillemets
Ce ne serait pas normal que Pycharm n'autorise pas une indentation autre que 2 espaces vu que c'est une recommandation de Python...

@+

Dernière modification par yoshi (27-04-2018 16:40:50)


Arx Tarpeia Capitoli proxima...

Hors ligne

#78 27-04-2018 16:35:18

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

Re : crible en python

j'ai trouvé la blague qui fermait la fenêtre .
à la fin dans la ligne :
os.system(pause) il n'y avait pas les ("pause")

voila pour n = 12000:

Donnez la valeur de n = 30k : 12000
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 1230 nombres premiers
Appuyez sur une touche pour continuer...

et tant qu'à faire n=3000 000 000

Donnez la valeur de n = 30k : 3000000000
Crible mod30 : Initialisation: 47.0496826171875 seconds ---
Crible mod30 : Famille de chaque Pi: 34.03925967216492 seconds ---
Crible mod30 : Criblage des 8 familles: 203.14035725593567 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 77.32933592796326 seconds ---
On a 135095831 nombres premiers
Appuyez sur une touche pour continuer...

un dernier n=3420000000 et ensuite je vais voir si je dépasse 3720 000 000

Donnez la valeur de n = 30k : 3420000000
Crible mod30 : Initialisation: 45.0372793674469 seconds ---
Crible mod30 : Famille de chaque Pi: 36.14526319503784 seconds ---
Crible mod30 : Criblage des 8 familles: 222.95559167861938 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 114.53540134429932 seconds ---
On a 153107189 nombres premiers
Appuyez sur une touche pour continuer...

au niveau rapidité on est toujours dans les 6 minutes pour 3 mds, je vais modifier F = j +p['i] *29 au lieu de 30...car je n'ai que les valeurs de j sans supplément ce qui ne change rien.. à piori c'est plus "stable" dans l'exécution...
je vais voir la limite.
ne t'embête pas pour charger pycharm ...Car il faut de toutes façon ne travailler que sur une Famille p8 = ['11'] ou fp = 11 ,par exemple 
ce qui permettra de réduire les recherches D_c ['3','5','7','9']  et j += incr etc etc. 

if d_c %2==0:
            j += p[i]
            d_c = j%10  # ça ne change pas en principe

la limite wile j < f , devrait être:  wile j != %30 == 11  car on travaille famille 11(modulo 30) ..si c'est comme cela qu'il faut l'écrire 
et enlever les lignes qui ne servent plus à rien, ainsi que l'initialisation qui se ferra sur une seule ligne ou colonne...

de ce fait on vérifie la décimale : d_c = '1' et si j 11%30== 0 sinon on passe au suivant  ce qui limitera aussi les calculs, la vitesse et on va plus loin ....etc

et tu m'envoies la facture...par mail...@+

Hors ligne

#79 27-04-2018 16:38:05

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

Re : crible en python

yoshi a écrit :

Salut,

D'abord rectifie la dernière ligne :
os.system(pause) ---> os.system("pause") (guillemets autour de pause)

Ça devrait venir de là !
@+

et oui ...j'étais en train de te répondre...

Hors ligne

#80 28-04-2018 07:16:15

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

Re : crible en python

Bonjour
@Yoshi ,voici un comparatif de temps entre l'ancienne version crible mod30 et ta nouvelle version CribleG3 mod30

on peut voir qu'en temps global il y a peu de différence et la limite maxi pour n est la même..


Donnez la valeur de N = 30k : 3690000000
Crible mod30 : Famille de chaque Pi: 128.8874261379242 seconds ---
Crible mod30 : Criblage des 8 familles: 472.961630821228 seconds ---
On a 164630426 nombres premiers
Appuyez sur une touche pour continuer...

Donnez la valeur de n = 30k : 3690000000
CribleG3 mod30 : Famille de chaque Pi: 56.830899715423584 seconds ---
CribleG3 mod30 : Criblage des 8 familles: 627.8699028491974 seconds ---
On a 164630426 nombres premiers
Appuyez sur une touche pour continuer...

Donnez la valeur de N = 30k : 3720000000
Crible mod30 : Famille de chaque Pi: 69.42012166976929 seconds ---
Crible mod30 : Criblage des 8 familles: 365.36824202537537 seconds ---
On a 165910122 nombres premiers
Appuyez sur une touche pour continuer...

Donnez la valeur de n = 30k : 3720000000
CribleG3 mod30 : Famille de chaque Pi: 35.318461894989014 seconds ---
CribleG3 mod30 : Criblage des 8 familles: 426.22394847869873 seconds ---
On a 165910122 nombres premiers
Appuyez sur une touche pour continuer...
 

j'ai à peu près compris le rôle de la fonction fam qui remplace l'indice ou la valeur de j (modulo 30) ; ainsi que la fonction jmod30 qui je suppose correspond à p8 [...]..

3. Comme les d_c que tu testais sont forcément impairs:
  a) les restes pairs sont écartés

c'est à dire , qu'un reste R pair , correspondant à R de 2n par p['i] est transformé en R['i] = j impair, en y ajoutant p['i] pour vérifier à qu'elle famille il appartient  et par rapport à sa D_c = [ 1,3,7,9]

  car D_c = '5' n'à pas lieu d'être testé, on peut donc directement ajouter 2*p['i] ..non ? au lieu de faire une division j%5==0 ??

Mais comme les multiples de 3 se terminent aussi par D_c = [ 1,3,7,9]. Est ce que cela serait pas plus facile de faire :
si  j = D_c==1  on teste si j %1 ==0 or j % 11==0 ; si l'un ou l'autre est oui, on passe au suivant en y ayant ajouté 2*pi...

sinon c'est un multiple de 3 et donc on passe au suivant..... ce qui éviterait peut être les divisions par 3 car il y en a pour chaque j, qui se termine par 1,3,7 ou 9 ce qui alourdi le programme....non ?

voila pourquoi il est aussi intéressant de ne travailler que sur une famille, quitte ensuite à modifier les paramètres de la famille pour en choisir une autre dans le programme...on teste uniquement la D_c de la famille en question avec une seule division...par exemple si on a fixée la famille fp = 1  si j = D_c==1 on fait j1%30==0 on le positionne et on crible avec son p['i] , sinon on passe au suivant j += 2*p['i]

puisque l'on a déjà tous les p ératosthène > 5, et leurs reste tel que  :  r.append(2*n % p['i]) ce qui donne :
si R est pair on ajoute p['i] et j = R['i] impair et on commence avec ce couple... si d_c =[3,5,7,9] on incrémente j += 2*p['i] et on passe au suivant.... ...etc

si R est impair donc = j , si D_c =[3,5,7,9] on incr = j += 2*p['i] ; si d_c ==1 on teste, si ok on positionne et on crible;  sinon on incr et on passe au suivant....


Passe un bon week end et merci pour ton aide et pour tout....

Dernière modification par LEG (28-04-2018 08:11:15)

Hors ligne

#81 28-04-2018 07:40:21

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Salut

1. Crible mod30 : Criblage des 8 familles: 472.961630821228 seconds ---
2. CribleG3 mod30 : Criblage des 8 familles: 627.8699028491974 seconds ---

Ma dernière version serait 30% plus lente ????
Waow : ça ne va pas du tout et je ne vois pas pourquoi...
Si c'est le cas, c'est illogique.
Je vais tout reprendre.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#82 28-04-2018 09:07:32

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

Re : crible en python

yoshi a écrit :

Salut

Si c'est le cas, c'est illogique.
Je vais tout reprendre.
@+

non ....il y a un écart de 6%, regarde pour 3 720 000 000 entre les deux versions...

après de toutes les façons, ils bloquent tous les deux à 3 750 000 000

l'écart peut venir de python...car par exemple pour l'initialisation il y a des différence qui ne s'explique pas...puisque l'on range le 8 familles en colonne et que les nombres sont des [1] qui représentent 30k + la premières cellule = P8

le criblage c'est différent tout dépend commente il procède :

1) il a les P['i] de p ératosthène >5 , dans les deux cas c'est pareil ...

2) il calcule les restes R de 2n modulo p['i]

donc il a ses couples R et P[i'] et j= r['i] c'est R += p['i] si R pair ou R impair  ...et += 2*p['i] si D_c==5

3) il prend le premier couple R et son p[i'] et la il va vérifier....

a) R pair il ajoute directement p[i'] cela devient j ...puis il va vérifier les j si j d_c ==5 il incrément += 2*p[i']
b) si d_c == [1,3,7,9] il va tester pour voir à quelle famille il appartient , pour ensuite le positionner dans sa famille et cribler cette famille avec son p['i] jusqu'au 8 familles .
alors est ce qu'il calcule les 8 j = R['i] ensuite il les place puis il cribles les 8 famille avec p[i'] en question.

ou est ce que lorsqu'il a j %30==11 "par exemple", avant de passer au suivant il le place de suite remplace la cell[1] par [0], il crible et il passe au j suivant, en ayant incr j+=2*p['i] jusqu'à ce qu'il ait fini p8 = [1.7.11.13.17.19.23.29]...?

Là est la question...????

c'est pour cela que dans mon dernier post je t'ai posé certaines questions pour éviter le %3==0...
pour ne vérifier et tester que les D_c==[1.3.7.9]...si jp8%30==0 sinon c'est un multiple de 3.

On a donc que deux divisions possibles par D_c==[1.3.7.9] soit 1 et 11 %30 ; 13 et 23 %30; 7 et 17 %30; 19 et 29%30...
D'autant que le quotient donne la position dans la famille :

Exemple  j = 191,  jD_c == 1; teste j11%30==0 donc famille 11 et position (191-11)/30 = 6 donc nbcll n°6 qui est la 7ème puisque l'on compte 0,1,2,3,4,5,6,7,8....<=n//30 
idem si j1%30==0
sinon c'est que c'est un multiple de 3 on incrémente on passe au suivant... etc pour les 8j.

Ce qui devrait donner dans l'ordre d'exécution n=15030 , on prend pi = 7 , calcul du Reste de 2n % 7, R==2  donc pair .


 2 +=7  donne j=R['i].on établit les 15j et on commence :

j==9 test j%30==19 or j%==29 ; suivant jincr += 2*7; j==23 test j%30==13 or j%==23 ok ,position 0 dans p8=[23] on change nbcell [1]en [0] et on crible...suivant j +=14 , j==37 test j %30==7 ok position 1 dans p8=[7] le [1] devient [0] on crible..j+=14 ,j==51; j%==1 or ==11 suiv;  +=14 , j==65 suiv; +=14 , j==79 ;j%30==19 ok position 2 dans p8[19] le [1]evient[0] on crible..retour..+=14 , j==93  test j% 13 or 23 , suiv +=14; j==107, j%30==7 or 17 ok position 3 dans p8[17] le [1]devient[0] on crible..retour +=14, j==121 test j%30==1 ok position 4 dans p8[1] , le [1]devient[0] on crible ..retour ; +=14, j==135 ; +=14,j==149 test j%30==19 or 29 ok position 4 dans p8[29] le [1]devient[0] on crible ..retour; +=14, j==163 test j%30==13  ok position 5 dans p8[13] le[1]devient [0], on crible .. retour ; +=14, j==177 , j%30==7 or 17 suivant ; +=14, j==191 test j%30==1 or 11 ok position 6 dans p8[11] le [1]devient [0] on crible... Les 8 familles p[8] sont finies.

 On réitère on prend le Pi suivant = 11, calcul du reste R = 8, j = 8+11 = 19 on incrémente pi*2 les 15 j et on recommence: .j==19 , test j%30 == 19 , ok position 0 dans p8=[19] le [1] devient [0], on crible avec 11....retour et suivant...etc etc
 

ensuite on passe au couple R et son p['i] suivant.... Ou bien on calcule tous les j puis on les place et on crible avec son p['i] , mais cela fait le double de manip en principe....

à la fin il n'y a pas de miracles puisque l'on compte que les nbcell==[1]  les cell[0] ne donne pas de premiers de n à 2n..

voila je pense que connaissant ton indentation et le fonctionnement du crible ça ne peut pas poser problème....pour voir qu'elle est la meilleur façon de programmer ...
@+

Dernière modification par LEG (02-05-2018 20:39:33)

Hors ligne

#83 28-04-2018 09:29:32

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Re,

J'ai dû regagner en vitesse par rapport à ma dernière version...
Mais je ne saisis pas :
- ta version chez moi est plus lente pour le tri de chaque famille que la mienne,
- ensuite, le criblage des 8 familles devient plus lent chez moi... Pourquoi ? J'ai plus de nombres à cribler ? A voir... C'est là que je perds du temps...

Pour n =24000000
Ton programme avec "litanie des if" :

Donnez la valeur de N = 30k : 24000000
Crible mod30 : Initialisation: 0.5080292224884033 seconds ---
Crible mod30 : Famille de chaque Pi: 10.330590724945068 seconds ---
Crible mod30 : Criblage des 8 familles: 2.159123420715332 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 1.209069013595581 seconds ---
On a 1381022 nombres premiers

Ma dernière version où je passe par un dictionnaire :

Donnez la valeur de n = 30k : 24000000
Crible mod30 : Initialisation: 0.5060291290283203 seconds ---
Crible mod30 : Famille de chaque Pi: 0.054003000259399414 seconds ---
Crible mod30 : Criblage des 8 familles: 2.279130458831787 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 1.2260701656341553 seconds ---
On a 1381022 nombres premiers

Donc, j'ai remplacé ma liste Jmod30 par un dictionnaire...
On y accède de la même façon qu'une liste, sauf que la syntaxe est {key:value}  et que value, peut être un nb, une chaîne ou.. une liste (et même un autre dico)...

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 = []
    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 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 d_c==5:  # on passe au suivant
                fam = -1
            else:                
                fam =Dico[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")

Tu as quelle version de Python ? 3.x surement, mais x= ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#84 28-04-2018 10:17:35

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

Re : crible en python

yoshi a écrit :

Re,

J'ai dû regagner en vitesse par rapport à ma dernière version...
Mais je ne saisis pas :
- ta version chez moi est plus lente pour le tri de chaque famille que la mienne,
- ensuite, le criblage des 8 familles devient plus lent chez moi... Pourquoi ? J'ai plus de nombres à cribler ? A voir... C'est là que je perds du temps...

Tu as quelle version de Python ? 3.x surement, mais x= ?

@+

non il ne peut pas y avoir plus de nombres car dans les deux cas tu as 24000000/30 = 800000 nombre[1] ou nbcell = n/30 * 1

ma version python est python- 3.6.4 amd (64bit)-webinstal ; version 3.6.4150.0 du 03 2018

Hors ligne

#85 28-04-2018 10:39:03

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

Re : crible en python

voila chez moi ta new version:

Donnez la valeur de n = 30k : 24000000
CribleG4 mod30 : Initialisation: 0.32760071754455566 seconds ---
CribleG4 mod30 : Famille de chaque Pi: 0.015599727630615234 seconds ---
CribleG4 mod30 : Criblage des 8 familles: 1.1076023578643799 seconds ---
CribleG4 mod30 : Extraction des premiers n à 2*n : 0.5304009914398193 seconds ---
On a 1381022 nombres premiers
Appuyez sur une touche pour continuer...

qui est plus rapide que sur ton pc...

ton ancienne version :

Donnez la valeur de n = 30k : 24000000
CribleG3 mod30 : Initialisation: 0.32760071754455566 seconds ---
CribleG3 mod30 : Famille de chaque Pi: 0.015600204467773438 seconds ---
CribleG3 mod30 : Criblage des 8 familles: 1.1232020854949951 seconds ---
CribleG3 mod30 : Extraction des premiers n à 2*n : 0.5304012298583984 seconds ---
On a 1381022 nombres premiers
Appuyez sur une touche pour continuer...

mon ancienne

Donnez la valeur de N = 30k : 24000000
Crible mod30 : Initialisation: 0.35880064964294434 seconds ---
Crible mod30 : Famille de chaque Pi: 0.015599966049194336 seconds ---
Crible mod30 : Criblage des 8 familles: 1.1232020854949951 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 0.5460009574890137 seconds ---
On a 1381022 nombres premiers
Appuyez sur une touche pour continuer...

c'est presque quif quif  ta dernière est plus rapide...

dans ton programme  à chaque fois je change le nom de la version en: crible , cribleG3 et G4 pour m'y retrouver et les lancer...

Dernière modification par LEG (28-04-2018 10:46:04)

Hors ligne

#86 28-04-2018 10:43:19

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Salut,

Ok, tu me rassures..
J'ai gratté un peu partout (purement technique), j'ai éliminé des calculs et des tests redondants : j'ai gagné du temps :


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 d_c %2==0:
            j += pi
            d_c = j%10        
        while j <= f:
            if j%3==0 or d_c==5:  # on passe au suivant
                fam = -1
            else:                
                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")

Sortie cette fois :

Donnez la valeur de n = 30k : 24000000
Crible mod30 : Initialisation: 0.5090291500091553 seconds ---
Crible mod30 : Famille de chaque Pi: 0.049002885818481445 seconds ---
Crible mod30 : Criblage des 8 familles: 1.91910982131958 seconds ---
Crible mod30 : Extraction des premiers n à 2*n : 1.2740728855133057 seconds ---
On a 1381022 nombres premiers

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#87 28-04-2018 10:54:47

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

Re : crible en python

je là copie et je re test  donc ce serra cribleG5 mopd30
résultat :

Donnez la valeur de n = 30k : 24000000
CribleG5 mod30 : Initialisation: 0.32760047912597656 seconds ---
CribleG5 mod30 : Famille de chaque Pi: 0.015599966049194336 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 1.029601812362671 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 0.5616011619567871 seconds ---
On a 1381022 nombres premiers
Appuyez sur une touche pour continuer...

là ça envoie.....LoLLLL

Hors ligne

#88 28-04-2018 11:09:03

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

Re : crible en python

test avec G5 :

Donnez la valeur de n = 30k : 3000000000
CribleG5 mod30 : Initialisation: 38.34886860847473 seconds ---
CribleG5 mod30 : Famille de chaque Pi: 3.7284064292907715 seconds ---
CribleG5 mod30 : Criblage des 8 familles: 170.47709965705872 seconds ---
CribleG5 mod30 : Extraction des premiers n à 2*n : 83.14814591407776 seconds ---
On a 135095831 nombres premiers
Appuyez sur une touche pour continuer...

on est passé de 40 minutes pour la version d'origine avec une limite à 900 méga en ayant modifié Eratosthène et compagnie  à
un peu moins de 4 minutes et 3720 méga...

voila un bon court pour les étudiants.... comment aller plus vite..... et surtout l'étude de ce crible , car quand même personne ne l'a fait...et personne à par toi l'a programmé....
@+

Hors ligne

#89 28-04-2018 11:13:25

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Re,

En gros, au total, chez toi, 1,93 s de traitement pour n =24000000. Bon, satisfaisant, alors...
Sur le plan technique, je suis au bout du bout du bout.
Maintenant, après le comment, pour gratter encore, je ne vais pas pouvoir faire l'économie du pourquoi...
Ça me permettrait de voir si la transcription en Python de la méthode ne peut pas être pensée différemment.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#90 28-04-2018 11:39:53

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

Re : crible en python

yoshi a écrit :

Re,

En gros, au total, chez toi, 1,93 s de traitement pour n =24000000. Bon, satisfaisant, alors...

c'est très très bon

Maintenant, après le comment, pour gratter encore, je ne vais pas pouvoir faire l'économie du pourquoi...
Ça me permettrait de voir si la transcription en Python de la méthode ne peut pas être pensée différemment.

@+

c'est à dire:  comment penser différemment ??
je ne vois pas ce que l'on pourrait  encore , dans ta dernière version je ne pense pas ....

la seule pensée différente  et de la méthode, reste la méthode par famille.... et Un bon restau...à ma charge non...???

cela permet de voir la répartition par famille...etc etc ..
déjà la fonction, N /ln 2N = pi(g) ("où pi(g) est la fonction qui compte les [1] donc les nombres premiers de N à 2N") est évidente avec ce crible , mais je laisse cela aux Matheux...il n'auront aucun mal à le démontrer rigoureusement ci l'envie leur prend.... personnellement c'est inutile car évident...
@+

Dernière modification par LEG (28-04-2018 11:42:23)

Hors ligne

#91 28-04-2018 12:55:36

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Salut,

Pour ta gouverne, explications  des modifs.
1. Technique. Python est relativement lent comme langage. Contrairement au C, C++ par exemple, il ne peut pas être compilé, i-e, transformé en langage machine... Les fonctions principale built-in comme on les appelle sont écrites en C donc bien plus rapides que tout ce que nous on peut programmer.
Par exemple
for i in range(lenp):
    j=p['i]
est plus lent que
for j in p:

Le problème est que parfois, tu as besoin aussi de l'indice, donc il existe une variante qui mixte les deux :
for i,j in enumerate(p):
qui permet d'extraire la valeur et son indice.
C'est l'équivalent de
i=0
for j in p:
    i=i+1
sauf que la gestion du compteur est extérieure : perte de temps.

2. Concernant le bloc :

if j%3==0 or d_c==5:  # on passe au suivant
       fam = -1
else:                
      fam =Dico[j%30]      
      if pfam[i][fam] == 0:
           pfam[i][fam] = j
j += incr
d_c = j%10

à la place de :

if j%3 ==0 or d_c==5:  # on passe au suivant
     fam = -1
else:                
     fam =Dico[j%30]      
if fam != -1 and pfam[i][fam] == 0:
       pfam[i][fam] = j
j += incr
d_c = j%10

Je me suis avisé d'un seul coup que on ne traitait l'instruction que si fam =!1 et que justement lorque  le else s'exécutait, alors  fam !=-1...
Et donc que if fam!=-1 était vérifié  même alors qu'on savait déjà que oui ou non.
Donc, je n'ai utilisé que
if  pfam['i][fam] == 0 que j'ai placé dans le else:
J'économisais ainsi le test if fam!=-1, et le if  pfam['i][fam] == 0 n'était plus testé pour toutes les valeurs de j...

3. Encore un gain de temps :

    for i in range(lenpfam):
        pi=p[i] n# --> avant il était en dessous du for j (*)
        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))

(*)... ce qui veut dire que le programme allait chercher p['i] systématiquement alors qu'il ne changeait qu'une fois sur 8.

4. Si dans une boucle où tu fais 24000000 de tours tu utilises plusieurs fois de suite p[ i], mieux vaut écrire une fois pi=p[ i] et utiliser la variable pi chaque fois ensuite.
En effet la référence de la liste p est rangée qq part en mémoire, cette référence c'est l'adresse de la liste à laquelle le prog va se rendre puis chercher le (i+1)e élément de cette liste...
Là je ne le fais qu'une fois et la valeur pi est stockée qq part et j'y accède toute de suite...
Pour 1000 tours de boucle, la différence n'est pas sensible, pour de très grands nombres, si !...

Ce n'est pas vraiment de la programmation, c'est de la logique mise au service de la chasse aux calculs/instructions inutiles et/où redondants.

En outre, ce que j'ai voulu dire, c'est qu'entre un procédé manuel et sa traduction en algorithme, il peut y avoir des différences selon ton inspiration, selon les programmeurs, donc le fond conditionne aussi la forme ; jusqu'à maintenant, je me suis essentiellement attaché à la forme (la technique).

Je prends un autre exemple simple.
La multiplication dite "arabe"...
Il n'y a gère qu'une seule méthode à la main, particulièrement simple : on y utilise une grille, et on effectue que des multiplications élémentaires issues des tables) et sans retenues, et des additions (avec retenues cette fois).
Pas grande technicité, hein...
Et pourtant, entre ma première version et la dernière, j'ai bien dû diviser le temps d'exécution par 2 !
Rien qu'en ayant une autre vision de la technique Python et en m'en tenant strictement à la technique manuelle réinterprétée et adaptée au traitement informatique...
http://www.bibmath.net/forums/viewtopic … 147#p68147  Posts #42 et 43

Vois-tu un programmeur fait ça par vice : il n'a pas besoin de récompense.
Mon 1er gros truc, sur mon premier ordi qui avait 64 ko de mémoire vive et des disquettes sur chaque face des desquelles, on stockait 180 ko  : j'ai écrit un programme de conjugaison complet qui pouvait soin conjuguer n'importe que verbe à ta place, toi tu le conjuguais et toi et la bécane corrigeait. J'étais en pourparlers pour une diffusion professionnelle, quand j'ai tout stoppé parce que l'éditeur voulait chambouler ma présentation... J'avais réussi un tour de force inégalé - à ma connaissance - aujourd'hui : le prog déterminait de lui-même si un verbe en "ir" était du 2e ou du 3e groupe sans lexique et en 10 lignes (6 mois d'analyse acharnée pour trouver).

Là, j'ai un autre fer au feu.
A la même époque, un copain m'avait refilé un programme d'astrologie (écrit en Basic) pour que le modifie.
15 ans après, je l'avais réécrit en TurboBasic et largement abondé...
Aujourd'hui, je voudrais le refaire en Python.
J'essaie donc de comprendre ce que j'avais bien pu bricoler à l'époque : je n'ai pas encore tout compris !!!
Il faut dire que le programme passé dans mon traitement de texte avec une police à espacement fixe, en taille 10 et avec marges mini occupe... 30 pages ! J'ai de quoi faire !

Quand je te parlais de "vice"...

@+

Je l'ai encore


Arx Tarpeia Capitoli proxima...

Hors ligne

#92 28-04-2018 14:03:50

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

Re : crible en python

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

Hors ligne

#93 28-04-2018 14:14:39

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

Re : crible en python

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

Hors ligne

#94 28-04-2018 17:14:56

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

Re : crible en python

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
11 #masqué , position n°0 dico 11:2 cribl ['1] = [0] , retour suivant
25 saute
39 != 9 et 19%30
53 ok
67 ok
81 != 1 et 11%30
95 saute
109 ok
123  != 13 et 23%30
137  ok
151  ok
165  saute
179  ok
193  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
 

Dernière modification par LEG (29-04-2018 03:52:40)

Hors ligne

#95 29-04-2018 07:53:38

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

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 ...
Voilà ce que contient r pour n=24000 :
[1, 7, 4, 9, 6, 22, 5, 12, 11, 30, 12, 13, 35, 33, 54, 28, 4, 39, 47, 26, 29, 82, 25, 2, 64, 40, 88, 121, 54, 50, 45, 22, 133, 115, 78, 71, 79, 28, 35, 59, 136, 129, 41, 103]
Tu peux y voir des nombres pairs, des multiples de 3 et de 5...
Donc, on ne peut pas, en l'état, faire l'économie du test if j%3==0 or d_c==5.

Pourtant, c'est un de mes objectifs, mais la clé est en amont et dans le incr...
j au départ n'est pas multiple de 3 : j%3 =0 ou j%3=2
Prends maintenant incr = 7 : 7%3=1
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...

Tiens au passage, encore une modif :
j'ai supprimé un test et une affectation.
Voilà le bloc modifié


        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

J'ai donc dû gratter encore un peu de temps...

@+

[EDIT] Tests avec n=1500
Je regarde les valeurs de j%3 juste avant la ligne
if j%3!=0 and d_c==5! :


 i     cyclicité de j%3
 0         2  1  0
 1         1  2  0
 2         2  1  0
 3         1  2  0
 4         2  1  0
 5         0  1  2
 6         1  2  0
 7         1  0  2
 8         0  2  1
 9         1  2  0
10         0  2  1
11         0  1  2
12         1  2  0

pi max :  53

Dernière modification par yoshi (29-04-2018 08:22:08)


Arx Tarpeia Capitoli proxima...

Hors ligne

#96 29-04-2018 09:39:26

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

Re : crible en python

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

Hors ligne

#97 30-04-2018 06:54:55

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

Re : crible en python

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

Hors ligne

#98 30-04-2018 08:15:53

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Salut, 

voilà pour n=240 :

i  pi    incr     j  incr%3  j%3
0   7     14      11   2      2
0   7     14      25   2      1
0   7     14      39   2      0
0   7     14      53   2      2
0   7     14      67   2      1
0   7     14      81   2      0
0   7     14      95   2      2
0   7     14     109   2      1
0   7     14     123   2      0
0   7     14     137   2      2
0   7     14     151   2      1
0   7     14     165   2      0
0   7     14     179   2      2
0   7     14     193   2      1
0   7     14     207   2      0

1  11     22       7   1      1
1  11     22      29   1      2
1  11     22      51   1      0
1  11     22      73   1      1
1  11     22      95   1      2
1  11     22     117   1      0
1  11     22     139   1      1
1  11     22     161   1      2
1  11     22     183   1      0
1  11     22     205   1      1
1  11     22     227   1      2
1  11     22     249   1      0
1  11     22     271   1      1
1  11     22     293   1      2
1  11     22     315   1      0
1  11     22     337   1      1  

2  13     26      25   2      1
2  13     26      51   2      0
2  13     26      77   2      2
2  13     26     103   2      1
2  13     26     129   2      0
2  13     26     155   2      2
2  13     26     181   2      1
2  13     26     207   2      0
2  13     26     233   2      2
2  13     26     259   2      1
2  13     26     285   2      0
2  13     26     311   2      2
2  13     26     337   2      1
2  13     26     363   2      0
2  13     26     389   2      2

3  17     34      21   1      0
3  17     34      55   1      1
3  17     34      89   1      2
3  17     34     123   1      0
3  17     34     157   1      1
3  17     34     191   1      2
3  17     34     225   1      0
3  17     34     259   1      1
3  17     34     293   1      2
3  17     34     327   1      0
3  17     34     361   1      1
3  17     34     395   1      2
3  17     34     429   1      0
3  17     34     463   1      1
3  17     34     497   1      2

4  19     38       5   2      2
4  19     38      43   2      1
4  19     38      81   2      0
4  19     38     119   2      2
4  19     38     157   2      1
4  19     38     195   2      0
4  19     38     233   2      2
4  19     38     271   2      1
4  19     38     309   2      0
4  19     38     347   2      2
4  19     38     385   2      1
4  19     38     423   2      0
4  19     38     461   2      2
4  19     38     499   2      1
4  19     38     537   2      0
4  19     38     575   2      2

Valeurs récupérées juste après le while j<=f:
et avant le if j%3=0 and d_c==5...

Je m'absente.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#99 30-04-2018 09:24:39

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

Re : crible en python

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

Dernière modification par LEG (30-04-2018 09:36:57)

Hors ligne

#100 30-04-2018 14:14:56

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 871

Re : crible en python

Salut,

Bon, déjà ce bloc remanié (références à d_c supprimées !) donne les bons résultats et un poil plus vite...

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

@+


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)?
quatre-vingt sept plus soixante et un
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