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

#176 06-05-2018 17:26:13

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

Re : crible en python

Re,

Pour 21 000 000 000
**  108684761 nombres trouvés en 293.2337155342102 secondes **
ou
**  108683085 nombres trouvés en 255.0136477947235 secondes **

Pourquoi 2 résultats différents ?

Pourqui=oi par deux fois quoter ce que tu avais déjà écri ?

Sinon, comme annoncé, j'ai revisité la def eratostène : plus de while, rien que des for...
Et pour 240 000 000 comme prédit, je n'ai gagné grand chose : 1/10e s...
Le gros du temps de l'initialisation, il est là :

    nombres = [[1 for _ in range(nbcell)] for _ in range(8)]

Et je doute qu'on puisse faire quoi que ce soit : chez moi, 5 s pour 240 000 000...
Chez toi 130 s/165 s pour  21 000 000 000

Après, il restera plus qu'à me repencher sur le criblage des 8 familles : chez toi, 108/105 s poir 21 000 000 000...
Après, ce sera : Game over !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#177 06-05-2018 18:31:11

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

Re : crible en python

yoshi a écrit :

Re,

Pour 21 000 000 000
**  108684761 nombres trouvés en 293.2337155342102 secondes **
ou
**  108683085 nombres trouvés en 255.0136477947235 secondes **

Pourquoi 2 résultats différents ?

je voulais te faire une blague avec le premier résultat...Mais à priori tu n'as pas vu..? la répartition du nombre de nombres premiers par famille ne peut Jamais être la même , chaque nombre premier étant unique, les départs ne peuvent JAMAIS être les mêmes pour une limite n fixée, il y aura donc un décalage que ce soit dans Eratothène ou dans G ....! la répartition des nombre premiers est oscillatoire en règle générale, mais aussi par Famille avec une même densité en moyenne générale, puisque les Pi criblent de façon identique les 8 familles...

Tu as un premier Résultat que j'ai indiqué , en criblant séparément deux familles a) la fam 30k+7 et  ensuite la fam 30k+13 :

Voici le nombre de premiers entre N et 2N , congrus à 17[30] l'autre au dessus je pense que tu avais vu la blague c'était  le nombre de premiers entre N et 2N congrus à 23[30] pour N = 21 000 000 000 :

Tu remarques que le temps à un écart de 30 secondes, mais avec une autre limite plus grande si c'était faisable , tu verrais les temps s'inverser..
passe de 1 200 000 000 par limite une dizaine de fois et tu le remarqueras en criblant qu'une famille  ex la 7 puis après la 13... n'oublies pas de changer Dico={7:0....etc } puis Dico={13:0......etc} et.. in range (8) en (1).
Sachant que cribler la famille 30k+7 , te donne le résultat de n à 2n pour la famille 30k+23 ... Goldbach..!

Pourqui=oi par deux fois quoter ce que tu avais déjà écri ?

j'ai dû faire une erreur de manipe en relisant ce post vers la page 4 et en modifiant certaines "de mes phrases..."



Après, il restera plus qu'à me repencher sur le criblage des 8 familles :

sur le criblage proprement dit , tu ne pourras pas changer grand chose en principe ...

car une fois que tu as tester pfam(0),les 8j  sont de la forme 30k + P8, [" peut être qu'on aurait dû les nommer Pj"] et que tu les as affecté à leur famille (("j==p8%30") = Pj ) ils vont marquer les 8 positions de départ pour Pi, et puis Pi cribles chacune des 8 fam, modulo Pi.

C'est à dire que si P[sub]i ==7[/sub] , et bien 7 va marquer du [0] toutes les 7 cell [1] comme le fait Eratosthène_mod30 lpar famille, et là, tu ne peux pas partir du carré de Pi...!

Ensuite serra le tour de 11 qui marquera d'un [0] toutes ses 11 cellules comme Eratosthène, même si une cellule est déjà marquée [0]  par 7, qui est passé avant c'est normale..

Dans Eratosthène , tu parts de 7 et tu marque tous ses multiples toutes les 7 cellules,  puis lorsque 11 part il marque tous ses multiples y compris 77 qui est déjà marqué par 7...

La différence qu'il y a dans E et dans G, c'est la position de départ...Qui pour le cribleG8Y est = ou < à Pi quel qu'il soit...! Ce qui par obligation entraine moins de nombres premiers q de n à 2n...! pour n >= à 30 donc pour Pi = 7 au minimum..qui donne les premiers de la famille 23[30]...

Alors que dans E , tu parts au minimum de Pi, ou de son carré...! forcément pour une même limite n tu marqueras moins de nombres...d'où = plus de premiers de 7 à n ; il n'y a rien à démontrer ! cqfd ...! d'où quelque soit n >= 30 il ne peut y avoir plus de nombres premiers q de n à 2n que de nombres premiers p de 7 à n

A+

Dernière modification par LEG (07-05-2018 06:39:36)

Hors ligne

#178 06-05-2018 22:30:39

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

Re : crible en python

Bonsoir
@Yoshi pour 300 000 000
les cribles G ne font aucune erreur de nombres;  ni par famille , mais attention de bien choisir la famille qui de 7 à n donne la famille de n à 2n
j'ai failli faire une bourde en vérifiant le nombres avec (nbpremier .win32)..la fatigue...(" je peux te le faire parvenir si cela t'intéresse"]

== RESTART: E:\executable algo P(30)\cribleG8y_modulo30 avec D_C - Copie.py ==
Donnez la valeur de n = 30k : 300000000
Phase d'initialisation: 3.619206190109253 seconds ---
Famille de chaque Pi: : 0.3120005130767822 secondes ---
Criblage des 8 familles: 9.188416004180908 seconds ---
Extraction des premiers n à 2*n : 0.6396009922027588 seconds ---

**  15 072 378 nombres trouvés en 13.759223699569702 secondes **

voici le résultat pour n= 600 000 000  -300 000 000 :Eratostenne. (la somme des différences )

Crible nbpremier win 32 par famille, somme des 8 familles<= 600 000 000  - somme des 8 familles <=300 000 000   :                                 =  >>>31 324 701 -16 252 323 = 15 072 378

@++
Bonne Nuit..

Dernière modification par LEG (07-05-2018 06:44:07)

Hors ligne

#179 07-05-2018 07:54:11

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

Re : crible en python

Bonjour
@Yoshi pour info:

j'ai demandé de cribler la famille 17[30] pour extraire les nombres premiers q [n ; 2n] de la famille 13[30]
== RESTART: E:\executable algo P(30)\cribleG8y_modulo30 avec D_C - Copie.py ==
Donnez la valeur de n = 30k : 21 000 000 000
Phase d'initialisation: 177.06031107902527 seconds ---
Famille de chaque Pi: : 14.383225202560425 secondes ---
Criblage des 8 familles: 104.36418318748474 seconds ---
Extraction des premiers n à 2*n : 5.31960916519165 seconds ---

**  108 685 119 nombres trouvés en 301.1273286342621 secondes ** Et BIen BRAVO car :

résultat de nbpremier-Win32 : fam13[30] temps total pour les deux extraction : 326'' secondes
1) jusqu'à 42 000 000 000
puis
2)jusqu'à 21 000 000 000

>Allocation du Tableau en cours...
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
41999999953
>trouvé à la position:
224226861
>Allocation du Tableau en cours...
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
20999999743
>trouvé à la position:
115541742

total de la différence = 108 685 119

G8Y est plus rapide car il n'a pas besoin de faire deux extractions...!
@++

Hors ligne

#180 07-05-2018 08:58:42

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

Re : crible en python

Bonjour,

  Encore un gain de vitesse...
Il m'est revenu en mémoire que la forme de création de liste en compréhension :
nombres=[[1 for _ in range(nbcell) for _ in range(8)]]
si elle était plus ramassée que la méthode classique, était par  conte plus lente...
Ça ne m'avait paru fondamental jusqu'à aujourd'hui, mais hier, j'avais constaté que le temps consommé par la phase d'initialisation était à 90 % celui de création de la liste nombres...
  Hier soir, cette remarque sur la vitesse m'est revenue en mémoire et ce matin au saut du lit (après le p'tit déj quand même), j'ai voulu en avoir le cœur net :


from time import time
from os import system

def eratostene(n):
    n = int((2*n)**0.5)
    m = (n-1) // 2
    limite=1+n
    b = [True]*m
    premiers = [2]
    for i,p in enumerate(range(3,limite,2)):
        if b[i]:
            premiers.append(p)
            j = 2*i*i + 6*i + 3
            debut,pas=j,2*i+3
            for j in range(debut,m,pas):
                b[j] = False
    debut=i
    for i in range(debut,m):
        if b[i]:
            premiers.append(p)
        p += 2
    return premiers[3:]

def Crible_mod30(n):
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n)
    nn,nbcell,nbcl=n*2,n//30,n//30-1
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)
    Pfam,P8=[],[1, 7, 11, 13, 17, 19, 23, 29]
    Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)

    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):
        Pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        for j in range(debut,fin,pas):
            Pf=Pfam[i]
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]      
                if Pf[fam] == 0:
                    Pf[fam] = j
    s_2=time()-start_time
    print("Famille de chaque Pi: : %s secondes ---" % s_2)
   
    #ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE pi
    start_time = time()
    for i,Pf in enumerate(Pfam):
        pi=Primes_init[i]
        for j in range(8):
            debut_index=(Pf[j] - P8[j])//30
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0
    s_3=time() - start_time
    print("Criblage des 8 familles: %s seconds ---" % s_3)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time            
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s_1+s_2+s_3+s_4,

n = int(input("Donnez la valeur de n = 30k : "))
nbr,s= Crible_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")
 

(ma version remaniée de la def eratostene, y est incluse...)

Et voilà la sortie :

Donnez la valeur de n = 30k : 240000000
Phase d'initialisation: 0.4170238971710205 seconds ---
Famille de chaque Pi: : 0.43302464485168457 secondes ---
Criblage des 8 familles: 10.50960087776184 seconds ---
Extraction des premiers n à 2*n : 0.6120350360870361 seconds ---

**  12194880 nombres trouvés en 11.971684455871582 secondes **

-4,5 s !!!

Je veux bien parier que toi, jonglant avec les dizaines de milliards, ça va être encore plus net !

Pour le criblage, a priori, je pense comme toi : je ne pourrai rien gagner...
Mais je vais regarder quand même !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#181 07-05-2018 09:12:53

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

Re : crible en python

Oui Mais comme tu as modifié for i in range [8] et for j in range(8) est ce que je dois mettre un (1) ) la place des deux (8), lorsque je sélecte une famille ...?

car actuellement je veux cribler uniquement la famille 17 [30] pour avoir le nombre de premiers 13 [30] de n à 2n,

1) je change les deux lignes".... in range (8] en "...in range(1) ok,
2) puis je change l'ordre dans Dico ={ 1:0,7:1,...etc } en Dico ={17:0,1,1:.....13:3,..etc}

je vais éssayer avec la version G4 qui par rapport aux autres est lente..et n'a plus d'intérêt techniquement...ok
@

Hors ligne

#182 07-05-2018 09:34:28

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

Re : crible en python

est bin dis donc , ça change tout .....!!!!

regardes,
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 24090000000
Phase d'initialisation: 2.610149383544922 seconds ---
Famille de chaque Pi: : 3.0521745681762695 secondes ---
Criblage des 8 familles: 125.56661677360535 seconds ---
Extraction des premiers n à 2*n : 6.0996105670928955 seconds ---

**  123968501 nombres trouvés en 137.32855129241943 secondes **

par rapport à tout à l'heure...:

== RESTART: E:\executable algo P(30)\cribleG8y_modulo30 avec D_C - Copie.py ==
Donnez la valeur de n = 30k : 24090000000
Phase d'initialisation: 344.167804479599 seconds ---
Famille de chaque Pi: : 24.304842948913574 secondes ---
Criblage des 8 familles: 122.96995878219604 seconds ---
Extraction des premiers n à 2*n : 6.406366586685181 seconds ---


**  123968501 nombres trouvés en 497.8489727973938 secondes **

wonderbar....lollll

ça influence énormément cette modification.....! Chapeau chapeau...

Moi qui voulait t'envoyer, nbpremier-win32...mais il ne sert plus à rien même si il crible ....>450 000 000 000 par famille..cela oblige le double de manipe pour soustraire...

je vais pousser pour voir où il n'en peut plus....

Hors ligne

#183 07-05-2018 10:33:03

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

Re : crible en python

Salut,

Content que tu sois très content...
Le nombre de nombres entiers traitable avec Python dépend en outre de la version de windows installée 32 ou 64 bits qui dépend de ta carte-mère...
En effet, windows 32 bits ne gère au grand maxi que 3,2 Go de RAM, mais windows 64 bits est très à l'aise avec 16 Go (ce que j'ai moi) :
- Or, le savoir te permettra de choisir entre Python 32 bis ou 64 bits
- et donc, comme corollaire, avec 16 Go de RAM, tu pousses plus loin la taille et la qté de nombres entiers gérables.

Quant au criblage, le seul angle d'attaque est dans cette ligne :

            debut_index=(Pf[j] - P8[j])//30

Il faut que je trouve une relation mathématique entre Pf[j] (c'est à dire Pfam['i][j]) et  P8[j] qui permette de prévoir - simplement ! - Pf[j] quand on a P8[j] qui aboutirait à simplifier le calcul de debut_index...
J'ai quelques doutes :-(

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#184 07-05-2018 11:19:05

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

Re : crible en python

j'espère que cela va te donner des idées sur la courbe de progression du temps de criblage par tranche de 300 000 000, ainsi que la courbe de progression du nombre de nombres premiers par famille de N à 2N....

pour les 8 familles c'est pareille, il n'y a que le nombres de premiers qui varient très très peu et en plus il est oscillatoire , en faisant les différence entre les tranches consécutivement, ont le remarque très bien , mais surtout il en est de même par famille pour Eratosthène modulo 30, j(avais poussé jusqu'à 450 000 000 000 par famille...

l'intérêt et bien ce genre de crible et son programme, qui le valide, c'est que l'on peut prouver par l'absurde, de façon très élémentaire; que la densité du nombre de nombre premiers de N à 2N reste en moyenne générale générale la même ...! "je pense que cela aurait plu à Chebotarev, pour son théorème..." ils avaient des idées mais pas de PC....

voici les résultats : on a criblée la famille 17 modulo 30 , pour obtenir le résultat de la famille 13 modulo 30 et on peut faire l'inverse bien entendu...

tu remarqueras, que la répartition est linéaire , y compris entre les famille...Tu vas me dire c'est pas étonnant ce serra toujours par tranche , et pour les 8 famille les mêmes nombres premiers qui crible...!


Donnez la valeur de n = 30k : 24900000000
Phase d'initialisation: 2.4381394386291504 seconds ---
Famille de chaque Pi: : 3.101177453994751 secondes ---
Criblage des 8 familles: 129.15738725662231 seconds ---
Extraction des premiers n à 2*n : 6.5163726806640625 seconds ---

**  127964502 nombres trouvés en 141.21307682991028 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 25200000000
Phase d'initialisation: 2.4551403522491455 seconds ---
Famille de chaque Pi: : 3.1511802673339844 secondes ---
Criblage des 8 familles: 129.49340653419495 seconds ---
Extraction des premiers n à 2*n : 6.560375213623047 seconds ---

**  129441051 nombres trouvés en 141.66010236740112 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 25500000000
Phase d'initialisation: 2.503143072128296 seconds ---
Famille de chaque Pi: : 3.1791818141937256 secondes ---
Criblage des 8 familles: 131.9785487651825 seconds ---
Extraction des premiers n à 2*n : 6.723384618759155 seconds ---

**  130919894 nombres trouvés en 144.38425827026367 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 25800000000
Phase d'initialisation: 2.504143476486206 seconds ---
Famille de chaque Pi: : 3.2011830806732178 secondes ---
Criblage des 8 familles: 133.23862075805664 seconds ---
Extraction des premiers n à 2*n : 6.721384525299072 seconds ---

**  132396824 nombres trouvés en 145.66533184051514 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 26100000000
Phase d'initialisation: 2.5521459579467773 seconds ---
Famille de chaque Pi: : 3.244185447692871 secondes ---
Criblage des 8 familles: 135.7970108985901 seconds ---
Extraction des premiers n à 2*n : 6.800388813018799 seconds ---

**  133871604 nombres trouvés en 148.39373111724854 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 26400000000
Phase d'initialisation: 2.5611462593078613 seconds ---
Famille de chaque Pi: : 3.2691872119903564 secondes ---
Criblage des 8 familles: 138.1088993549347 seconds ---
Extraction des premiers n à 2*n : 6.8693928718566895 seconds ---

**  135348431 nombres trouvés en 150.8086256980896 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 26700000000
Phase d'initialisation: 3.9902281761169434 seconds ---
Famille de chaque Pi: : 4.5902626514434814 secondes ---
Criblage des 8 familles: 140.21626377105713 seconds ---
Extraction des premiers n à 2*n : 6.962398052215576 seconds ---

**  136822700 nombres trouvés en 155.75915265083313 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 27000000000
Phase d'initialisation: 2.638150691986084 seconds ---
Famille de chaque Pi: : 3.3951942920684814 secondes ---
Criblage des 8 familles: 141.773108959198 seconds ---
Extraction des premiers n à 2*n : 7.048403263092041 seconds ---

**  138297746 nombres trouvés en 154.8548572063446 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 27300000000
Phase d'initialisation: 2.646151065826416 seconds ---
Famille de chaque Pi: : 3.4261958599090576 secondes ---
Criblage des 8 familles: 143.90347480773926 seconds ---
Extraction des premiers n à 2*n : 7.1124067306518555 seconds ---

**  139770860 nombres trouvés en 157.0882284641266 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 27600000000
Phase d'initialisation: 2.6761529445648193 seconds ---
Famille de chaque Pi: : 3.453197717666626 secondes ---
Criblage des 8 familles: 144.89228749275208 seconds ---
Extraction des premiers n à 2*n : 7.185410976409912 seconds ---

**  141245269 nombres trouvés en 158.20704913139343 secondes **
>>>
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 27900000000
Phase d'initialisation: 2.773158550262451 seconds ---
Famille de chaque Pi: : 3.814218044281006 secondes ---
Criblage des 8 familles: 144.63127279281616 seconds ---
Extraction des premiers n à 2*n : 7.259414911270142 seconds ---

**  142717739 nombres trouvés en 158.47806429862976 secondes **
>>>

Hors ligne

#185 07-05-2018 12:03:23

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

Re : crible en python

yoshi a écrit :

Salut,

Quant au criblage, le seul angle d'attaque est dans cette ligne :

  debut_index=(Pf[j] - P8[j])//30

Tu peux me détailler exactement ce que fait cette ligne, avec un ou deux exemples :

car ce que je pense comprendre,  c'est la relation qu'il y a entre les 8 j d'une pfam , par exemple les 8, de pfam(0) et don Pi==7; {"puisque pour chaque changement de valeur de la limite n +30, on réitère en repartant de Pi==7..."}

et les P8j une fois les testes %30 fait, afin de les positionner dans leur famille...ensuite Pj ou Pi crible...

pour moi c'est la méthode du programme qui va réduire les divisions qui peuvent rentrer en jeu c'est tout....je suppose.....

Exemple: j'ai mon premier j en partant de R...ok  donc j(0), qui peut être R,des l'instant où il est impair...!

Moi je faisais %9 trois solutions possibles sur un seul teste ok...j'ai vu aussi qu'il ne se termine pas par 5 car sinon != (incr == 2*pi)

j'obtiens  :
a) : {1,4,ou7} ;
par conséquent il appartient une des 4 familles {1,7,13 et 19} ok en fonction de sa D_c je connais exactement sa famille ...je part le positionner et je crible avant de passer au pf[j] suivant...

b): j'obtiens {0,3, ou 6} multiple de trois != icnr..

C) : j'obtiens {2,5, ou 8} par conséquent il appartient une des 4 familles {11,17,23 et 29} ok en fonction de sa D_c je connais exactement sa famille ...je part le positionner et je crible avant de passer au pf[j] suivant...

donc le cas A) est C),  sont identiques...! ça ne fait pas l'hombre d'un doute...

la seule relation que je vois entre Pf[j] et P8[j] c'est le reste modulo 9 qui sont différents, du fait que 4 familles sont de la forme 3k +1
et les 4 autre ; 3k -1...

Quant au positionnement  avant le départ du criblage et bien il dépend du quotient ...uniquement  car par exemple si tu as un Pj ==30k +7
qui fait 4 chiffres où 5...le plus simple c'est c'est (P8[j] - 7)//30 = quotient, entier par obligation :
donc la position dans P8 , est par le N° du quotient..!

Si le quotient ==127 et bien cellule 127  si tu préfaire le 127 ème nombre qui est == (127*30) + 7 , puisque la première cellule a pour N° 0


Il faut que je trouve une relation mathématique entre Pf[j] (c'est à dire Pfam['i][j]) et  P8[j] qui permette de prévoir - simplement ! - Pf[j] quand on a P8[j] qui aboutirait à simplifier le calcul de debut_index...


J'ai quelques doutes :-(

je ne pense pas ...car c'est pf[j] qui détermine P8[j] , pas l'inverse...du fait que c'est  pf[j]  qui détermine à quelle famille P8, il appartient ..!

Dernière modification par LEG (07-05-2018 12:07:39)

Hors ligne

#186 07-05-2018 12:47:51

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

Re : crible en python

Re,

debut_index=(Pf[j] - P8[j])//30

Tu peux me détailler exactement ce que fait cette ligne, avec un ou deux exemples :

Question étonnante, car cette ligne ou du moins quand j'écris index =int((Pfam['i][j] - P8[j])/30) est de toi...
Peut-être que ta question vient de  :
debut_index =...
Dans tes versions précédentes, tu écrivais :


    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]
 

Faut pas croire, je n'ai rien inventé : le créateur, c'est toi, moi, je suis le technicien Python, c'est tout...
Donc, je t'avais dit :
- les boucles while me donnent des boutons
- c'est plus lent qu'une boucle for, puisque ça t'oblige à gérer, toi, un compteur avec un incrément que tu choisis (ici  pi, soit p['i])
Donc, j'ai réfléchi au moyen d'en faire une boucle for...
Ici, il me fallait écrire
for truc in (debut,fin,pas):  au lieu de while index<nbcell:...

Il était clair que truc, c'était index, que fin=nbcell et après vérification attentive,  index+=pi me donnait le pas....
Restait debut...
Avant ton while,  tu initialisais index à 

int((pfam[i][j] - p8[j]) / 30)

, je me suis dit que je tenais debut :

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

qui est devenu par suite

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

en utilisant le quotient entier...

Donc


    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]

est devenu :


    for i in range(lenpfam):
        for j in range(8):
           debut_ index = int((pfam[i][j] - p8[j]) // 30          
            for index in range(debut_index, nbcell,p[i]:
                nombres[j][index] = 0
 

Puis :


    for i,Pf in enumerate(Pfam):
        pi=Primes_init[i]  # ton ex p[i]
        for j in range(8):
            debut_index=(Pf[j] - P8[j])//30
            for index in range(debut_index, nbcell,pi):
                nombres[j][index] = 0

Cela dit, j'ai trouvé qq chose : chez moi, pour n=240000000 c'est tantôt un poil plus rapide, tantôt un poil plus lent , sans certitude absolue que pour n > 240000000 le nombre de premiers extrait reste le bon...
Je creuse encore, parce que je ne suis pas vraiment satisfait.
Je te le livre "as is" :
remplacement de

debut_index=(Pf[j] - P8[j])//30

par 

debut_index=Pf[j]//10//3

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#187 07-05-2018 13:48:53

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

Re : crible en python

il n'y a rien d'étonnant , car lorsque je demandais le rôle de certaine ligne de programme à mon petit fils , c'est pas grave ça va être trop long à t'expliquer...!donc:

debut_index=(Pf[j] - P8[j])//30

je ne comprend pas exactement ce langage..cette ligne ..

d'après moi, si 2n%pi == r ==4 on index c'est à dire on ajoute pi , c'est la début de l'index....; puis on regarde ou teste si j ==P8%30...sinon effectivement, on a pas le choix ...> jusqu'à wile à cause des 8 j d'une pfam qui n'ont  et ne peuvent pas avoir un ordre bien défini quelque soit n....

à l'inverse d'Eratosthène modulo 30 où des que tu rencontres un pi premier, et bien il part est crible ...> jusqu'à n
et tu n'as en tout est pour tout que 8 premiers de base == P8 où 1 est remplacer par 31 bien évidemment ...!
que l'on peut apparenter à pfam[0] est qui reste invariable ...quelque soit n par famille , car pour chaque famille,
ce n'est pas la même position mais ces 8 pfam sont unique et on toujours le même positionnement car ce la correspond au produit des cellule de départ...

ton reste en fonction de Pi et de n...il est trop variable et tu ne peux en principe éviter la boucle wile pour n > 31² == 961 donc 990 ...!
là, il te faut aller est indexer jusqu'à wile: f== pi*29 sauf si tu imposes une autre contrainte qui est : des que les 8 conditions sont connues et bien on crible... OR :
Actuellement je ne sais toujours pas si le programme crible une fois qu'il a positionné les 8 pj... puis famille après famille

où si il crible au fur et à mesure, qu'il place un pj remplissant la condition [ j  -  p8%30 == 0];
{'" pour être sûr qu tu me comprennes, cela veut dire par exemple si: j = 127; alors 127 -p8 % 30 == 0, ; pour P8 == 7""} donc il rempli la condition, d'où on le place dans sa famille 30k +7 , et 0n crible avec Pi en question...pour passer au "pf[j]" suivant...

Donc et supposons que le programme à obtenu ses 8 pf[j] == p8%30...et bien on passe au couple de Pi et R suivant , on ne va pas juqu'à la boucle Wile ... mais c'est remplacer chat par un autre chat..car tu auras quand même la condition, c'est d'avoir tes [8 pf[j] - p8[j]] qui cela est vrai n'iront pas tous forcément jusqu'à la limite wile: j<= f...actuellement...

c'est peut être pour cela que personne n'a découvert ce crible....! qui est,  et,  tu en conviens relativement élémentaire mon cher Yoshi....

Moi dans excel: en partant de R , j'ai mes 8 j ("je vais ou je ne vais pas jusqu'à la limite < = pi*29) ; je fais mon mask des 8j , et copie collé dans mes 8 colonnes P8 ....>n//30

mon mask c'est 8 colonnes avec la position des 8pf[j] et de Pi lignes , que je copie pour aller le coller dans le tableau que j'ai initialisé avec des nbcell[1]
mais pour un nombre de ligne qui' n'excède pas Pi == 73; car le mask à copier coller est grand...

Ce qui veut dire que tu modifies tes lignes de programme, car tu en connais la signification exact , leur rôle, et ce qu tu en attends d'elle...ainsi que leur définition...

Moi je peux t'expliquer le fonctionnement du crible, ce qu'il faudrait qu'il fasse du mieux que je peux, mais en langage cro-magnon... et avec des exemples...heureusement tu en as compris le principe....

les lignes que j'ai modifier pour en arriver à cribler par famille c'est par tatonement et par des essais cas par cas , pas.. par ce que je savais ce que faisait tel ou tel ligne du programme...je le faisais à l'instinct , par rapport à ce que je pensais avoir compris...

Dernière modification par LEG (07-05-2018 13:58:08)

Hors ligne

#188 07-05-2018 14:03:59

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

Re : crible en python

Salut,


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

Tu veux dire que tu ne comprends pas cette ligne, depuis qu'elle figure dans ton programme, depuis l'origine ???
Bon alors, je vais relancer pour n = 240, et te donner les indications chiffrées que je peux récupérer...

Dans l'attente, est-ce que tu peux me dire si tu as essayé ma dernière suggestion de modif ?
Si oui, le résultat chiffré est-il correct au-delà de 240 000 000 ?
Le temps est-il supérieur, inférieur ?

Bon, je passe à l'extraction des données et je reviens...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#189 07-05-2018 15:03:04

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

Re : crible en python

je t'ai donné la liste des résultat post de 11h19 au dessus ...jusqu'a 27 900 000 000 on été bloqué à 23 9400 000 000 et je ne connais pas encore la limite maxi....

avec ma dernière version G9Y  que j'ai modifié ce matin et qui comporte bien:


 #ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE pi
    start_time = time()
    for i,Pf in enumerate(Pfam):
        pi=Primes_init[i]
        for j in range(1):
            debut_index=(Pf[j] - P8[j])//30
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0
    s_3=time() - start_time
 

qui est excellente !!!

Si oui, le résultat chiffré est-il correct au-delà de 240 000 000 ?
Le temps est-il supérieur, inférieur ?

 

on a presque divisé le temps par deux 1/2 ; par rapport à G8Y , toujours pour une famille criblée..!
regarde les résultats du post de ce matin à 9h34..

pour ta question effectivement je ne comprend pas exactement ce que fait cette ligne de programme...!
pas plus qu'il m'a fallut attendre Hier soir en faisant les testes par famille, que ce que l'on croyait cribler était en faite les familles complémentaires de Goldabch c'est en vérifiant avec [nbpremier win32] ("Eratosthène modulo 30, qui lui crible de 7 à N") que le résultat que j'imprimai :[  print (nombre) ] était en fait, pas le résultat de la famille que j'étais en train de cribler de n à 2n, mais celui de sa famille complémentaire ...ce qui ne change rien sur le résultat final des 8 familles , mais famille par famille c'est différent..

1) résultat pour 240 000 000 : 1 seconde...
========== RESTART: E:\executable algo P(30)\cribleG9Y_modulo30.py ==========
Donnez la valeur de n = 30k : 240000000
Phase d'initialisation: 0.07800030708312988 seconds ---
Famille de chaque Pi: : 0.062400102615356445 secondes ---
Criblage des 8 familles: 0.8736014366149902 seconds ---
Extraction des premiers n à 2*n : 0.06240034103393555 seconds ---

**  1524685 nombres trouvés en 1.076402187347412 secondes **

2 ) un exemple des 8 familles cribler pour n = 150 , je t'imprime les nombres , c'est à dire les cellules où le crible, commence dans un sens ou dans l'autre ce que l'on pourrait croire ,or il n'en ai rien grâce à Dico ={....} qui m'a fait comprendre le sens du criblage dans le programme...

CribleG6 mod30 : Initialisation: 0.0 seconds ---
CribleG6 mod30 : Famille de chaque couple R et Pi: 0.0 seconds ---
CribleG6 mod30 : Criblage des 8 familles: 0.0 seconds ---
CribleG6 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

cette première colonne criblée par la famille 1[30]

[0, 1, 1, 0, 1] corespond au nombre premiers de la famille 29 [30]

179  +121
0     +91 marqué ==[0]
239  +61
269  +31
0     +1 marqué [0]

..............................................

Dernière modification par LEG (07-05-2018 15:07:35)

Hors ligne

#190 07-05-2018 15:16:26

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

Re : crible en python

C'est aussi pour ça que maintenant, lorsque je crible, je t'indique quelle famille et le résultat de la famille complémentaire à Goldbach

je t'ai indiqué fait attention lorsque tu choisis de cribler une famille p81, le résultat que tu vas obtenir est celui de 2n - P81 = P829

Dernière modification par LEG (07-05-2018 15:17:03)

Hors ligne

#191 07-05-2018 17:14:54

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

Re : crible en python

Re,

Désolé, je me suis absenté...
n=240
nbcell=240//30=8 (de 0 à 7)
Primes_init=[7, 11, 13, 17, 19]  récupérés grâce à l'appel à la def eratostene.
Pfam :
[
[151, 67, 11, 193, 137, 109, 53, 179],                --->Pf =   Pfam[0]  ;  pi=Primes_init[0] = 7
[271, 7, 161, 73, 227, 139, 293, 29],                  --->Pf =   Pfam[1]  ; pi=Primes_init[1]  =11
[181, 337, 311, 103, 77, 259, 233, 389],            --->Pf =   Pfam[2]  ; pi=Primes_init[0] = 13
[361, 157, 191, 463, 497, 259, 293, 89],             --->Pf =   Pfam[3]  ; pi=Primes_init[0] = 17
[271, 157, 461, 43, 347, 499, 233, 119]              --->Pf =   Pfam[4]  ; pi=Primes_init[0] =19
nombres (version initiale):
[
[1, 1, 1, 1, 1, 1,1, 1],   ---------->Nombres_j =  nombres[0]
[1, 1, 1, 1, 1, 1, 1, 1],  ---------->Nombres_j =  nombres[1]
[1, 1, 1, 1, 1, 1, 1, 1],  ---------->Nombres_j =  nombres[2]
[1, 1, 1, 1, 1, 1, 1, 1],  ---------->Nombres_j =  nombres[3]
[1, 1, 1, 1, 1, 1, 1, 1],  ---------->Nombres_j =  nombres[4]
[1, 1, 1, 1, 1, 1, 1, 1],  ---------->Nombres_j =  nombres[5]
[1, 1, 1, 1, 1, 1, 1, 1],  ---------->Nombres_j =  nombres[6]
[1, 1, 1, 1, 1, 1, 1, 1]   ---------->Nombres_j =  nombres[7]
]


nbcell = n/30 = 8 
nombres (version finale) :
[
[1, 1, 1, 1, 1, 0, 0, 1],  ---------->  nombres[0]
[0, 1, 0, 1, 1, 0, 1, 1],  ---------->  nombres[1]
[0, 1, 1, 1, 1, 0, 0, 0],  ---------->  nombres[2]
[1, 0, 0, 0, 1, 1, 0, 1],  ---------->  nombres[3]
[1, 1, 0, 1, 0, 1, 1, 0],  ---------->  nombres[4]
[1, 1, 1, 0, 0, 1, 1, 1],  ---------->  nombres[5]
[1, 0, 1, 1, 1, 1, 1, 0],  ---------->  nombres[6]
[0, 1, 0, 0, 1, 0, 1, 1]  ---------->  nombres[7]
]

Donc
Pour chacun des Pf d'indice i de 0 à 4
     Exemple le Pf n° i = 1 qui est : [271, 7, 161, 73, 227, 139, 293, 29]
         Pour chaque élément  repéré par son indice  j de 0  à 7
              on calcule le début des indices : debut_index
              Exemple avec j=0 : Pf[0] c'est Pfam[1][0] qui vaut 271
              ici debut_index= (271- 11)//30 = 9    (Le 1 c'est P8|0])
              Pour chaque index de 9  à  8 par pas de 7
                   on passe immédiatement au debut_index suivant correspondant à j=1 parce que 9>8

              j=1 --> Pfam[1][1] vaut 7
              debut_index = (7-7)/30 = 0  (le 2e 7 c'est P8[1])
              Pour index de 0 à 8 (8, c'est nbcell) par pas de pi=11 (ici p[1] ou Primes_init[1]=11)
                     index = 0
                     nombres[1][0] =0
Vérification : [0, 1, 0, 1, 1, 0, 1, 1],  ---------->  nombres[1]
Le 1 en position [1][0] dans la liste nombres initiale est changé en 0.
L'ensemble de tous les debut_index est :
[
[5, 2, 0, 6, 4, 3, 1, 5],
[9, 0, 5, 2, 7, 4, 9, 0],
[6, 11, 10, 3, 2, 8, 7, 12],
[12, 5, 6, 15, 16, 8, 9, 2],
[9, 5, 15, 1, 11, 16, 7, 3]
]

Est-ce que ça t'aide ?

@+

[EDIT]

je t'ai donné la liste des résultat post de 11h19 au dessus ...jusqu'a 27 900 000 000 on été bloqué à 23 9400 000 000 et je ne connais pas encore la limite maxi....

avec ma dernière version G9Y  que j'ai modifié ce matin et qui comporte bien:

 #ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE pi
    start_time = time()
    for i,Pf in enumerate(Pfam):
        pi=Primes_init[i]
        for j in range(1):
            debut_index=(Pf[j] - P8[j])//30
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0
    s_3=time() - start_time

qui est excellente !!!

    Si oui, le résultat chiffré est-il correct au-delà de 240 000 000 ?
    Le temps est-il supérieur, inférieur ?

Je crois bien que tu as répondu à côté :
1. Je t'avais demandé une petite vérification en remplaçant la ligne debut_index=(Pf[j] - P8[j])//30 par  : debut_index=Pf[j]//10//3
2. De me dire si le nombre de premiers trouvés était bon même avec n> 240 000 000
3. De me dire ce que ça change en vitesse chez toi.

Dernière modification par yoshi (07-05-2018 18:54:46)


Arx Tarpeia Capitoli proxima...

Hors ligne

#192 07-05-2018 20:05:19

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

Re : crible en python

Bien sûr, vous travaillez dans le programme avec des indexes et vous comptez bien par pas de Pi dans la phase 2....pour chaque début d'index, mais dans la phase 1; famille de pi :
tu as traité les [j] construit les pfam et elles sont déjà "indexé" par famille et surement par Dico={.....}

Or dans cette phase 1 , si pfam[0] est déjà ordonné par famille  [j] devrait déjà être indexé...est donnée :pfam[0] indéxé..

{1:0,  7:1, 11:2, 13:3 , 17:4, 19:5 ,23:6 ,29:7}

[151,  67, 11,   193,   137,  109,   53,   179],                        --->Pf =   Pfam[0]  ;  pi=Primes_init[0] = 7
[(5), (2), (0), (6),  (4),   (3),    (1),   (5)]    les indexes --->Pf =   Pfam[0]  ;  pi=Primes_init[0] = 7
.

voila ce que je pensai : dans l'ordre:
n=240
nbcell=240//30=8 (de 0 à 7)
Primes_init=[7, 11, 13, 17, 19]  récupérés grâce à l'appel à la def eratostene.
............R=[4,  7, 12 , 4 ,  5]
puis :
phase (1) famille de pi tu as traité les 3m et 5m au fur est à mesure

j= [11, 53, 67, 109 , 137 ,179 , 193, 151] les [j] à partir de là, phase 1, (tu peux obtenir l'indice et l'index) moi je faisais:

J[0]== 11,  d_c == 1 , 11%9 == 2 ok 11 = Dico%30 == 0 , et 11:2 index 0 puis par pas de 7==[0]...> nbcell.retour
J[1] == 53 , D_c== 3 , 53%9 == 8  ok 53 = Dico%30 == 1, et 23:6 index 1 puis par pas de 7==[0]...>nbcell et retour
J[2] == 67 , D_C==7, 67%9 == 4  ok 67 = Dico%30== 2  et  7:1  index 2, puis par pas de 7==[0]>nbcell et retour
J[3] == 109 ,D_c== 9, 109%9 == 1  ok109 Dico%30 == 3 et 19:5 index 3, par pas de 7 ==[0] ...>nbcell retour
J[4]==137 , D_c==7, 137%9 ==2 ok, 137Dico%30== 4  et 17:4   index 4, par pas de 7==[0]...>nbcell retour
J[5] == 179, D_c == 9 179%9 == 8 ok 179 Dico%30 ==5 et 29;7 index 5 , par pas de 7==[0] ...Nbcell retour
J[6]==193,  D_c== 3  193%9 ==4 ok 193 Dico%30  ==6 et 13:3 index 6, par pas de 7==[0] ..>nbcelle retour
J[7] == 151 D_c== 1  151%9 ==7 ok 151 Dico%30  ==5 et  1:0 index 5, par pas de 7==[0] ..>nbcelle  fin pour pi==7 retour

au Pi suivant ==11 et pfam[1] réitération...  comme ci dessus...

[271, 7, 161, 73, 227, 139, 293, 29],                  --->Pf =   Pfam[1]  ; pi=Primes_init[1]  =11
..............................................................
colonnes = p8
[1 ,7 11,13,17,19,23,29]

  phase 3 criblage :

pfam[0] et pi[0]=7, par pas de 7, )à partir de l'index ....> nbcell

[(5),(2),(0), (6), (4), (3), (1), (5)]

[1, 1, 0, 1, 1, 1,1, 1],   -ligne ,nombre(0)
[1, 1, 1, 1, 1, 1, 0, 1],  -----,------   (1)
[1, 0, 1, 1, 1, 1, 1, 1],  -----,------- (2)
[1, 1, 1, 1, 1, 0, 1, 1],  -----,--------(3)
[1, 1, 1, 1, 0, 1, 1, 1],  -----,--------(4)
[0, 1, 1, 1, 1, 1, 1, 0],  -----,--------(5)
[1, 1, 1, 0, 1, 1, 1, 1],  - ---, --------(6)
[1, 1, 0, 1, 1, 1, 1, 1]   -----,--------(7)

nbcell = n/30 = 8 lignes , initialisation des 8 colonne de cellules qui se fait au début..du programme
...............................

*****************************************************************************************************

Pfam : ok tu as été jusqu'à la limite indiquée par donc j wile <= f == pi*29
étant donnée que les pfam [n] sont initialisées dans la phase 1, puis les [j] sont indexés par leurs famille , Dico={1:0,7:1,11:2,.....29:7}//30

sans les 3m et 5m alors, elles restes dans l'ordre :

[(5),(2),(0), (6), (4), (3), (1), (5)]  par pas de 7........> nbcell
[151, 67, 11, 193, 137, 109, 53, 179],   --->Pf =   Pfam[0]  ;  pi=Primes_init[0] = 7 :

["donc tu as fait un calcul pour ordonner les [j] de pfam[0], par rapport à leur famille...en éliminant les 3m et 5m; A priori  cette phase est rapide....vu le test avec G9Y
Puis tu recalcules les indexes, ([j] - Dico [8])//30 pour ensuite cribler par pas de Pi...ok..."] c'est ce que je ne comprenait pas (indice, index..moi je disais position.. ["mais c'est vrai, une fois que le langage serra compris est défini dans ma tête ça ira..ça ira..."]

Donc il se peut que ma méthode, soit plus compliquer et moins rapide..que ta méthode mais dans la phase 1 :on peut indexer avec les D_c , et %9 sachant qu'à la base: si %9 == (2,5,8) ....> alors p8 =={11,17;23 29} et D_c == {1, 7, 3,9} dico%30 == {11:2,17:4;23:6,29:7} d'où le quotient donne l'index dans sa famille d'où, il ne reste plus qu'à marquer d'un[0] sa cell et par pas de Pi, marquer ses cell.[0]..> nbcell et il sort.

la limite peut toujours rester <= F==pi*29, car des l'instant où le dernier J[7] de sa pfam[n] à fini et indiqué l'index pour Pi et que ce dernier à fini de marquer [0] par pas de pi dans sa famille ...>nbcell. La limite était pour cette pfam j <= F== (R +29*30) = 214 ne serra pas atteinte par le dernier[j] ...

Peut être que c'est pour cette raison qu'il a indexé comme cela ....?,
Mais il t'a fallu sacrément décrasser et réordonner...Je ne sais pas si cette forme ci dessus pour indexer %9 et indiquer les familles, te donnera des idée , du gain de temps, {"du fait que les indexes ne sont plus à "calculer"après avoir ordonné les pfam[n]..
la il sont invariables., quelque soit n . Car les D_c et %9 sont invariable seule le quotient de %9 qui va donner l'index de [j] va changer, en fonction de la limites 2n%pi qui donne les couples pi et  les reste R... Dans les deux cas c'est pareil...

En tous les cas, il marche à merveille ,tu as pu t'en rendre compte avec les résultats que tu m'as demandés...

*******************************************************************************

[181, 337, 311, 103, 77, 259, 233, 389],            --->Pf =   Pfam[2]  ; pi=Primes_init[0] = 13
[361, 157, 191, 463, 497, 259, 293, 89],             --->Pf =   Pfam[3]  ; pi=Primes_init[0] = 17
[271, 157, 461, 43, 347, 499, 233, 119]              --->Pf =   Pfam[4]  ; pi=Primes_init[0] =19

ok je comprend , tu as les 5 pfam indice de 0 à 4, et leur pf ......>ok.....................>0k

********************************************************************************

voila pour cette soirée , j'espère que j'ai été compréhensif...et que ton avis serra très bien venu...avec un GRAND Merci
@+ Yoshi..Gilbert.

Dernière modification par LEG (08-05-2018 07:05:16)

Hors ligne

#193 07-05-2018 20:12:17

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

Re : crible en python

c'est pareil , la ligne de ce matin par rapport à celle de ce soir ci dessous , ce matin c'était avec  une famille je n'avais pas remis range (1) en (8)

Donnez la valeur de n = 30k : 240000000
Phase d'initialisation: 0.3432004451751709 seconds ---
Famille de chaque Pi: : 0.10920023918151855 secondes ---
Criblage des 8 familles: 7.285212755203247 seconds ---
Extraction des premiers n à 2*n : 0.49920082092285156 seconds ---

**  12194880 nombres trouvés en 8.236814260482788 secondes **
>>>

Bonne soirée...

Dernière modification par LEG (07-05-2018 20:22:15)

Hors ligne

#194 08-05-2018 09:03:06

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

Re : crible en python

Re,

Là, ça devient compliqué de te suivre...

Donc il se peut que ma méthode, soit plus compliquer et moins rapide..que ta méthode mais dans la phase 1 :on peut indexer avec les D_c , et %9 sachant qu'à la base: si %9 == (2,5,8) ....> alors p8 =={11,17;23 29} et D_c == {1, 7, 3,9} dico%30 == {11:2,17:4;23:6,29:7} d'où le quotient donne l'index dans sa famille d'où, il ne reste plus qu'à marquer d'un[0] sa cell et par pas de Pi, marquer ses cell.[0]..> nbcell et il sort.

1. Encore une fois, ce n'est pas ma méthode : moi, je n'ai fait qu'optimiser ce qui était déjà écrit en Python, soit par toi, soit par ton petit-fils

2. Ça un fait un moment que je ne comprends rien à ce genre de notation : si ??? %9 == (2,5,8) que mets-tu à la place de "???" et pourquoi ? Qu'est-ce que la phase 1 ? Initialisation ?
    Depuis le début, je n'ai fait que me concentrer sur le crible donnant le nombre global de nombres premiers entre n et 2n.
   Apparemment, toi tu es capable de cribler spécifiquement ces premiers selon leur terminaison 1,3,7 ou 9 ? (Je n'en suis pas là : je me concentré sur un point à la fois.)
   Qu'est-ce que vient faire le %9 ? Pourquoi 9 ? c'est une 4 terminaisons ci-dessus ?
   C'est quoi 2,5,8  ?

3.  dico%30 == {11:2,17:4;23:6,29:7} : je ne peux pas comprendre ce que tu veux dire. Ça n'a pas de sens ni en Python, ni en quelque langage de programmation que ce soit...
    Dico%30 : tu ne peux obtenir que le reste de la division d'un nombre par 30, pas d'un dictionnaire entier :
   

>>> Dico=Dico={1:0,7:1,11:2,13:3,17:4,19:5,23:6,29:7}
>>> Dico%30
Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    Dico%30
TypeError: unsupported operand type(s) for %: 'dict' and 'int'

>>>

   D'autant que 1, 7, 11, 13, 17, 19, 23, 29 sont déjà les restes modulo 30 de tous les nombres premiers entre n et 2n

4.

[(5),(2),(0), (6), (4), (3), (1), (5)]  par pas de 7........> nbcell

    Tu veux dire quoi avec pas de 7---> nbcell ? que nbcell= 7 ? Dans le dernier programme, où je l'ai introduite expressément,  la notion de pas existait déjà de façon floue avec incr = pi (soit p['i]) et ici pi =p[0]=7
   Quant nbcell, pour n=240, c'est 240//30 soit 8. Alors pourquoi : "par pas de 7 ---> nbcell"

5. Tu as de la chance, que l'emploi du nom de variable index (je te l'ai déjà dit) n'ait pas amené d'erreurs, parce que index est un mot-clé du langage (une "méthode" de liste très précisément) et que ce n'est pas une bonne idée que de le faire (vivement déconseillé en Python).
    Que fait donc "index" ? 
    Çà :
   

>>> Pf=[151,  67, 11,   193,   137,  109,   53,   179]
>>> Pf.index(109)
5
Vérification :
>>> Pf[5]
109
>>>

    Avec les chaînes de caractères, c'est 'find"
   

>>> A="mfd%#k$Z12"
>>> A.find("#")
4
Vérification :
>>> A[4]
'#'
>>>

6. Je pense que tu as compris que mon long post précédent répondait à ta demande :
     

debut_index=(Pf[j] - P8[j])//30

    Tu peux me détailler exactement ce que fait cette ligne, avec un ou deux exemples :


Je retiens des posts qui précèdent que j//10//3 à la place de (Pf[j] - P8[j])//30 n'apporte rien en vitesse. D'un côté tant mieux, parce que la
nouvelle formulation était moins claire que la précédente et ça, ça me gênait...

Je vais essayer de résumer tes deux posts précédents en deux questions pour dissiper le brouillard :
* J'ai eu l'impression que tu disais avais trouvé un moyen de te passer de ce calcul (Pf[j] - P8[j])//30 ?. Vrai/Faux. Si c'est vrai, on va encore gagner du temps... Si non, là, je pense que c'est fini. Plus de gain possible...
* Quelque chose te gène encore dans le programme Python ? Si oui, quoi donc ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#195 08-05-2018 11:30:06

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

Re : crible en python

1. Encore une fois, ce n'est pas ma méthode : moi, je n'ai fait qu'optimiser

, ok pour moi ç'est tout comme puisque cela à modifier les blocs initialisation ,famille pi , criblage,

2) tu imprimes les temps des 4 phases :S1 : initialisation; S2: famille pi ; S3 : criblage et  S4.extraction.
initialisation :
prendre les Pi d'Eratosthène ,
création du tableau :
nn,nbcell,nbcl=n*2,n//30,n//30-1
    nombres=[]
    for i in range(8):
        nombres.append([1]*nbcell)

les famillesP8 =[..] et Dico ={...}
.....................................................
je ne comprends rien à ce genre de notation : si ??? %9 == (2,5,8) que mets-tu à la place de "???"  les 16 j , de R à f= j+2*pi
et pourquoi ?
.

pour éviter de faire deux fois le travail en calculant fam dans S2: et ensuite les index dans S3: ce que tu m'as expliqués hier et qui sont la phase crible   cette ligne dans S.2 positionne les "J" fam:
[fam = Dico[j%30]     
        if Pf[fam] == 0:   , tel que ton EX ..............>: pfam(0) ;  Pf=    [151,  67, 11,   193,   137,  109,   53,   179]
dans S.3 on calcul les index.:.......>debut_index=(Pf[j] - P8['j])//30...>  [(5), (2),(0),  (6),      (4),  (3),    (1), (5)] 
.........................................................................................................................................................
le j%9 , permet de tout faire en une étape si  ... d'abord on vérifie les Décimales d_c = j%10J donc si j != D_c==5 on passe au suivant
on a indiqué :    ... " l'ordre de Dico est déjà établi en phase S1"....

A_): si le reste de j %9 == [0,3 6] alors j est multiple de 3 on passe à j suivant

B_):si j %9 ==[1,4,7]  alors j appartient à fam , P8= [1, 7, 13 , 19] et donc si  j = D_c== [1, or 7, or 3, or9], l'index de Pf[j] serra:

debut_index=(Pf[j] - P8['j])//30
            Nombres_j=nombres[j]

.............................................................explication........................................................................................
[" il donne l'index: le quotient , c'est à dire la position ou rang de Pf[j] dans sa famille Dico=[1:0,7:1,13:3,19:5] puis il va marquer [1] en[0]   par pas de pi = 7..donc par pas de 7, toutes ses cellules  seront marqué [0] jusqu'à ...> nbcell qui est le nombres de cellule définie par n//30...  on revient à la suite des j, pour le j suivant.... on réitère   : donc on a la position de [j] et sa famille, il part cribler..pour ensuite passer à j suivant..jusqu'au dernier j qui serra de toutes les façon, <= f== j + pi*29 ..."]
....................................................................................................................................................

sinon:

C_): si j %9 ==[2,5,8]  alors j appartient à fam ,P8= [11 , 17 , 23 , 9} d'où si  j = D_c== [1, or 7, or 3, or9], l'index de Pf[j] serra:
debut_index=(Pf[j] - P8[j])//30 
            Nombres_j=nombres[j]   
qui donne le quotient, donc l'index,  P8j on connais sa place dans Dico={11:2, 17:4, 23:6 ,29:7......}  pf[j] par pas de pi = 7..va marquer toutes ses cellules, qui seront marquées [0] jusqu'à ...> nbcell qui est le nombres de cellule définie par n//30...("principe d'eratosthène")
................................................................................
c'est ce que tu m'as expliqué hier dans ton dernier post  et ma réponse,  on peut  faire S2 et S3  en une étape , [j] après [j] avec le reste %9;  Exemple j=151 : j%9== 7, donc se terminant par 1 c'est la famille 1[30] et Pf[J] - P8[j]//30 == 5 ; l'index ,le rang, la position.. P8[j] = 1  la famille {1:0} dans Dico...on place [j] dans la celllule 5 qui par pas de 7 va marquer d'un[0] ses cellules .....> nbcell == n//30.
..................................................................................
:S2
fam =Dico[j%30]     
                if Pf[fam] == 0:
                    Pf[fam] = j
............................................................
S3:
for j in range(8):
            debut_index=(Pf[j] - P8[j])//30
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,pi):
                Nombres_j[index] = 0
..................................................................................
dans la phase S2 : le programme crée les J à partir du reste R ...>jusqu'à  f=j+2*pi

for i,pi in enumerate(Primes_init):
        Pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        for j in range(debut,fin,pas):
            Pf=Pfam['i]
            if j%3!=0 and j%5!=0:

il classe les j impairs par famille qui ne sont pas 3m , 5m
par :   fam =Dico[j%30]     
                if Pf[fam] == 0:
                    Pf[fam] = j

.............................................
les index il m'a dit que c'était plus facile et rapide ...je lui est dit tu en est sûr...il m'a regardé de haut en rigolant....

4.

p8= [1....7...11...13..17...19...23...29]

..   [(5),(2),(0), (6), (4), (3), (1), (5)] 

par pas de 7. pour chaque colonne (famille) ....>lmite  nbcell==n//30

Tu veux dire quoi avec pas de 7---> nbcell ? que nbcell= 7 ? :
attention ceci  sont les index de ta pfam(0) avec Pi(0) = 7, dans les 8 colonnes de P8j , donc tu comptes par pas de 7 en partant de chaque index , marquer [0] ses cell......> limite nbcell = 8 dans l'exemple que tu as cité , dans tes explications...
.........................................

pour moi index je n'en savais rien ...pour moi pf[j] ==151 , est placé au rang 5, famille 1[30] et 151 est  dans la liste des j le cinquième sans les 3m et 5m..., Pf[j] =193 est le dernier de pfam(0) pour Pi(0) une fois que le dernier Pf[j] a criblé, on passe au couple Pi(1) R(1)
et on réitère ...Pourquoi établir une pfam(1), alors que l'on traite au fur et à mesure les pf[j]...? suite aux explication que tu m'as fournie....

dans le processus des phases S1, (S2.S3)== S3, puis S4 devient S3....à mon sens ...@+

Dernière modification par LEG (08-05-2018 13:30:47)

Hors ligne

#196 08-05-2018 11:44:56

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

Re : crible en python

re :

* J'ai eu l'impression que tu disais avais trouvé un moyen de te passer de ce calcul (Pf[j] - P8[j])//30 ?. Vrai/Faux.

par ce que je pensais, d'après tes explications d'hier soir;  tu me donnes les 5 pfam , indice de 0à 4

dans l'ordre des famille P8j comment ...?
je pensais que c'était le programme avec Dico= {1:0,......29:5} qui les avait classé pour ensuite calculer les index...pour moi cela fait deux calcul....
car comment le programme peut classer:
pfam(0) ;  Pf=[151,  67, 11,   193,   137,  109,   53,   179]   il faut qu'il utilise Dico={......}  et ensuite aller calculer les index...?

pf[j] =151 est le cinquième  des j....R +2pi......+pi....

Hors ligne

#197 08-05-2018 13:59:10

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

Re : crible en python

Salut,

car comment le programme peut classer:
pfam(0) ;  Pf=[151,  67, 11,   193,   137,  109,   53,   179]   il faut qu'il utilise Dico={......}  et ensuite aller calculer les index...?

Ca se "cache" ici :

# Pfam est déclarée avant dans l'initialisation : Pfam=[]  
    # FAMILLES POUR CHAQUE Pi
    start_time = time()

    for i,pi in enumerate(Primes_init):
        Pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
        r=nn%pi
        debut,fin,pas=r+pi*(1-r%2),1+r+pi*29,pi*2
        for j in range(debut,fin,pas):
            Pf=Pfam[i]
            if j%3!=0 and j%5!=0:
                fam =Dico[j%30]      
                if Pf[fam] == 0:
                    Pf[fam] = j

Pour n =240.nbcell = 240//30 =8
Pimes_init=[7,11,13,19]          (provient de la def eratostene)
Et on commence :
    Pour i, pi dans Primes_init :       #On passe chaque pi, en revue -> i ==0 - -> pi=7 ; pour  i==1 -->  pi =11, pour i==2  --> pi =13...
         On ajoute (à chaque nouvelle valeur de i) [0,0,0,0,0,0,0, 0] dans Pfam. Pour i == 0, on démarre donc avec Pfam = [[0,0,0,0,0,0,0, 0]]

(........................)

* description *
r=  480 % pi, donc r prendra les valeurs 480%7, 480%11, 480%13, 480%17 et 480%19 c'est à dire :  4, 7, 12, 4 et 5
Pour chaque i, pour pouvoir exécuter la boucle suivante, on utilise (r%2 qui vaut =0 ou 1)
debut=r+pi*(1-r%2) pour i = 0, debut =4+7*(1-0)=11 ; pour i =1, debut =7+7*(1-1) = 7 ; pour i=2 debut = 12+7*(1-0) =19...
fin =1+r+pi*29, pour i ==0, fin = 1+4+7*29 = 208, pour i ==1, fin =1+ 7+11*29 =327, pour i==2, fin =1+ 12+13*29 = 390...
pas=pi*2 : pour i==0, pas = 7*2 =14, pour i == 1, pas = 11*2 = 22, pour i == 2, pas = 13*2 =26
...
* fin description *

(........................)

On reprend
        Pour i =0, debut = 11, fin = 208, pas = 14.
On rentre dans la boucle
On a  i =0
    j prend la valeur debut, soit 11
    Pf prend la valeur Pfam[0], donc Pf= [0,0,0,0,0,0,0, 0]
   (Et là on teste j)
   A-t-on j%3==0 ou j%5==0 ?
   Non.
   | Donc fam =Dico[j%30]=Dico[11%30]=Dico[11] , soit fam=2. Et puisque Pf[2] (c'est à dire Pfam[0][2]) ==0,  à la place du 0, on écrit 11.
   |Sinon, on ne fait rien et on passe au j suivant
   |On alors Pf=[0, 0, 11, 0, 0, 0, 0,0] et automatiquement Pfam=[[0, 0, 11, 0, 0, 0, 0,0]]
   |Si la réponse avait été oui, on serait passé directement au j suivant...
   On vient d'inscrire le 11, on passe au j suivant : j=11+pas = 25

   (Et là on teste le nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 25+14 = 39

   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 39+14 = 53

   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Non.
     Donc fam =Dico[j%30]=Dico[53%30]=Dico[23] , soit fam=6. Et puisque Pf[6] (c'est à dire Pfam[0][6]) ==0,  à la place du 0, on écrit 53.
     On a alors Pf=[0, 0, 11, 0, 0, 0, 53, 0] et automatiquement Pfam=[[0, 0, 11, 0, 0, 0, 53,0]]
     et on passe au j suivant : j = 53+14 =67
etc...
    Le dernier j à être testé (quand i == 0) sera j=193...

Quand on a testé tous les j possible, on sort de la boucle et  prend la valeur 1.
Pfam devient [[151, 67, 11, 193, 137, 109, 53, 179], [0, 0, 0, 0, 0, 0, 0, 0]]
debut = 7, fin = 327 et pas = 22
On commence donc à j =7 et on repart jusqu'à 327 maxi...

C'est long à décrire, mais c'est ce que j'appelais suivre le prog ligne par ligne, avec crayon et papier...

@+

[EDIT]

Pourquoi établir une pfam(1), alors que l'on traite au fur et à mesure les pf[j]...? suite aux explications que tu m'as fournie..

Je n'en sais strictement rien, je n'ai fait qu'optimiser "bêtement", le programme fourni et gagnant 60% en vitesse...
Peut-être que le déroulement des opérations ci-dessus sera de nature à t'éclairer. Je te le souhaite

Dernière modification par yoshi (08-05-2018 14:06:58)


Arx Tarpeia Capitoli proxima...

Hors ligne

#198 08-05-2018 15:26:56

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

Re : crible en python

ça se cache plus précisément avec ton explication, qui est très limpide et qui explique le prog ligne par ligne ...!
c'est pour cela que je te disais dans mon langage pourquoi ne pas avoir utilisé le quotient de Dico%30
                fam =Dico[j%30]     
.....................................................
donc : dans ce processus ci de-ssous:

A-t-on j%3==0 ou j%5==0 ?
   Non.
   | Donc fam =Dico[j%30]=Dico[11%30]=Dico[11] , (OK ..et le quotient pourquoi ne pas l'utiliser..?)
, soit fam=2. Et puisque Pf[2] (c'est à dire Pfam[0][2]) ==0,  à la place du 0, on écrit 11Alors que l'on aurait dû écrire (0) qui serra le rang , l'index..à cet étape ..Non...?

suite:

(Et là on teste le nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 25+14 = 39

   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?
   Oui. On passe directement au j suivant : j = 39+14 = 53

   (Et là on teste ce nouveau  j)
   A-t-on j%3==0 ou j%5==0 ?

non:

Donc fam =Dico[j%30]=Dico[53%30]=Dico[23] , soit fam=6., est le quotient = (1)..?

Ok 

Et puisque Pf[6] (c'est à dire Pfam[0][6]) ==0,  à la place du 0, on écrit 53 alors que on aurait dû écrire (1) l'index = le rang .

On a alors Pf=[0, 0, (11), 0, 0, 0, (53), 0]  au lieu de et automatiquement Pfam=[[0, 0, (0), 0, 0, 0, (1),0]] ...

Ce qui fait Bien éviter le processus : dans le criblage :

for j in range(8):
            debut_index=(Pf[j] - P8[j])//30
            Nombres_j=nombres[j]

suite :

[ etc.."Le dernier j à être testé (quand i == 0) sera j=193..."] Tout à fait...

Quand on a testé tous les j possible <= f == pi*29 donc <= f == 7*29 , on sort de la boucle et  prend la valeur 1.
Pfam devient [[151, 67, 11, 193, 137, 109, 53, 179], Au lieu de [(5),(2),(0), (6), (4), (3), (1), (5)]

........................D'OÛ:...............

Il ne reste plus qu'à cribler les 8 familles par pas de pi =7 en partant des index = rang en mettant les [0] à la place des [1] ainsi que tous les 7 pas...jusqu'au rang 8 car il n' y a que 8 rang : 480/30 =8

Puis passer au pi(1) = 11

debut = 7, fin = 327 et pas = 22

... EXACTEMENT......

Au lieu de faire deux fois les travail..En recommençant dans la phase S3, le calcule des index avec pfam(0)  et criblage...????
quel est ton avis...??

déjà , même en modifiant ce processus  illogique..ça gagne du temps, même en faisant d'une traie pfan(0)==  [(5),(2),(0), (6), (4), (3), (1), (5)] puis aller cribler, c'est simplifier énormément..
alors que l'on pourrait même, cribler au fur et à mesure que pfam(0) se rempli de ses index....mais est que l'on aurait simplifié et gagner du temp.....pas sur.

car une fois pfam(0) construite : [(5):0,(2) :1 ,(0):2, (6):3, (4):4, (3):5, (1):6, (5):7] pf[j] fait des aller retour  , il prend ses index, change le [1] en [0] ....crible...> par pas de 7, ...> limite nbcell= 480/30= 8... etc les 8 familles..Fin .
les 8 famille sont criblée avec pi=7 . Retour au processus suivant avec pi=11...!

car déjà on y voit plus clair et même très clair , tu peux d'ailleurs, vraiment t'en faire une idée de ce qu'il aurait dû faire....

Dernière modification par LEG (08-05-2018 15:35:41)

Hors ligne

#199 08-05-2018 16:53:05

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

Re : crible en python

Salut,


 #ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE pi
# Là, on vient de construire Pfam qui avec n= 140 vaut ;
Pfam=[
[151, 67, 11, 193, 137, 109, 53, 179],
[271, 7, 161, 73, 227, 139, 293, 29],
[181, 337, 311, 103, 77, 259, 233, 389],
[361, 157, 191, 463, 497, 259, 293, 89],
[271, 157, 461, 43, 347, 499, 233, 119]
]
# 5 sous-listes de 8 nombres.
# Avec ce Pfam,  tu aboutis à une liste nommée nombres qui, à l'initialisation,  est constituée de 8 sous listes ne contenant que des 1 (au nombre de 8--> nbcell). Le traitement donne au final :
nombres = :
[
[1, 1, 1, 1, 1, 0, 0, 1],
[0, 1, 0, 1, 1, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0, 1],
[1, 1, 0, 1, 0, 1, 1, 0],
[1, 1, 1, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 0],
[0, 1, 0, 0, 1, 0, 1, 1]
]
#  8 sous listes de 8 (=nbcell)
*  Rappel : le premier 8 vient d'ici :
    for i in range(8):
        nombres.append([1]*nbcell)
* Ledit 8, qui ne changera pas, étant - apparemment - dû au fait que tu as 8 familles P8=[1,3,7,11,13,19,23,29]

Tu me poses des questions, c'est sympa, mais je ne maîtrise pas le pourquoi de ce qui est fait, alors te donner un avis serait plutôt gonflé de ma part de répondre...
Ce que je vois,  c'est que tu passes d'une liste (Pfam) de 5 sous-listes de 8 nombres à une liste de 8 sous-listes de 8 nombres...

Il y a peut-être un moyen, pour moi de contourner la difficulté, parce que
* ta liste nombres, elle ne me parle pas
* ta liste Pfam guère mieux (que sont ces nombres dans Pfam, comment les qualifies-tu ?)..
J'ai établi la liste des candidats à la primature entre 240 et 480 de deux façons :
[
[241, 243, 247, 251, 253, 259, 263, 269],
[271, 273, 277, 281, 283, 289, 293, 299],
[301, 303, 307, 311, 313, 319, 323, 329],
[331, 333, 337, 341, 343, 349, 353, 359],
[361, 363, 367, 371, 373, 379, 383, 389],
[391, 393, 397, 401, 403, 409, 413, 419],
[421, 423, 427, 431, 433, 439, 443, 449],
[451, 453, 457, 461, 463, 469, 473, 479]
]
et :
[
[241, 271, 301, 331, 361, 391, 421, 451],
[243, 273, 303, 333, 363, 393, 423, 453],
[247, 277, 307, 337, 367, 397, 427, 457],
[251, 281, 311, 341, 371, 401, 431, 461],
[253, 283, 313, 343, 373, 403, 433, 463],
[259, 289, 319, 349, 379, 409, 439, 469]
[263, 293, 323, 353, 383, 413, 443, 473],
[269, 299, 329, 359, 389, 419, 449, 479]
]
Si je prends la liste nombres comme un masque, où les 0, font disparaitre les nombres qui sont dessous, sur laquelle des deux listes présentées tu appliquerais le masque, pour faire apparaître les nombres premiers ?
La première, la seconde, ni l'une ni l'autre ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#200 08-05-2018 18:21:50

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

Re : crible en python

[P8]
.
.
(1)  .[1, 1, 1, 1, 1, 0, 0, 1],  ...> sens du criblage .....>nbcell =240/30 =8
(7)  .[0, 1, 0, 1, 1, 0, 1, 1],
(11) .[0, 1, 1, 1, 1, 0, 0, 0],
(13) .[1, 0, 0, 0, 1, 1, 0, 1],
(17) .[1, 1, 0, 1, 0, 1, 1, 0],
(19) .[1, 1, 1, 0, 0, 1, 1, 1],
(23) .[1, 0, 1, 1, 1, 1, 1, 0],
(29) .[0, 1, 0, 0, 1, 0, 1, 1],

ce masque ci dessus, va marquer les entiers en progression arithmétique de raison 30 ... car on travaille dans les 8 suites 30k +[P8...] d'oû
les 1 feront apparaître les nombres premiers q [n ; 2n] appartenant aux 8 famille complémentaires
[1,  7, 11, 13, 17, 19, 23, 29] =P8
[29,23,19,17,,13,,11,,7,, 1(31)] car 1 n'est pas premier, le complémentaire de 29 serait 31... de
ce masque indique par conséquent les entiers qui sont congrus à 2n (modulo Pi) donc, les nombres de cette pfam pour n=240;
Pfam=[
[151, 67, 11, 193, 137, 109, 53, 179],........> sont congrus à 480 [7] ou congru à 4[7]
[271, 7, 161, 73, 227, 139, 293, 29],........>sont  congrus à 480 [11] ou congru à 7[11]
[181, 337, 311, 103, 77, 259, 233, 389],....>sont  congrus à 480 [13] ou congru à 12[13]
[361, 157, 191, 463, 497, 259, 293, 89],.....> sont congrus à 480 [17] ou congru à 4[17]
[271, 157, 461, 43, 347, 499, 233, 119].......>sont congrus à 480 [19] ou congru à 5[19]
sont: les entiers qui sont congrus à 480[pi]

Eratosthène : tu parts de Pi et tu barre les multiple de Pi tous les Pi nombres...!

Goldbard : tu parts du reste R, de 2n par Pi, et tu barres les "congruents de Pi"  ou les nombres congrus à R [Pi],tous les Pi nombres...!

les [0] sont les congrus à R [pi] les [1] sont les non congrus à R[pi] (" un entier qui est congru à 2n[pi] est aussi congru à R[pi]")

d'où la valeur des [1] dans le tableau on s'en fou, ils prennent de la mémoire, inutilement ..c'est pour cela que l'on travaille uniquement avec les [ j] de R à f =j+2*pi , afin d'avoir  pfam qui positionne les points de départ marqué par [0] à la place du [1] et que l'on marquera tous les pi cellule par famille pour les 8 familles avant de passer à Pi(1) et pfam(1)...

attention à la taille du masque pour le dupliquer ...des masque de 8 [0] réparti sur Pi lignes est 8 colonnes , contenant pi cellules de [1] sauf les 8 [0] ..bien sûr, car par mask comme par pfam tu n'as que 8 index un par colonne..!

Si tu prends à la fin du criblage de tes 8 colonnes, et de tes n/30 lignes un 1 au hasard,  est bien il n'est pas congru à 2n[pi], et si tu veux connaître sa valeur c'est simple
(n) de la ligne , colonne = Famille P8[1,7,11,13,17,19,23,29]  puis : N°(n) * 29 + P8 = ((n)-1) *30 + P8

Exemple dans ton tableau d'entiers en progression arithmétique de raison 30 ; 371-P8)/30 = 12 te donne le n° de ligne ..l'indice..12

Et comme tu m'as fait une Blague en remplaçant la colonne n°2 par des 3m , je la remplace par les 30k+17 que je remet colonne 5 , 17[30] et je placerait mon mask dans le tableau arithmétique de raison 30...

Dernière modification par LEG (09-05-2018 08:23:42)

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 huit moins quarantequatre
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