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

#1 14-02-2020 09:26:05

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

Fusion de deux cribles

Bonjour
@Yoshi
suite à notre discussion sur ce projet , je pense que l'on peut le poser sur le forum...?

Donc voila la première partie du crible Ératosthène , un peu épuré des fonctions inutiles ; qui va servir de base pour utiliser le tableau d'Ératosthène criblé , dans ce programme , je pense qu'il est alors inutile de calculer 

 total= sum(crible)

mais on aura besoin de retourner le tableau criblé je suppose que la fonction serra :

 return "crible:",crible

qui va être utiliser par Goldbach dans la fonction :


def GCrible(premiers, n, fam):
    start_crible = time()
    crible = n//30*[1]     # Ou: on rapelle le tableau Ératosthène criblé de N/30 cases
    lencrible = len(crible)
 

j'ai bien essayé mais Nada....

je viens de supprimer cette première partie , afin d'éviter une erreur, car j'ai remis les crible post# ci-dessou suite à tes questions



attention :
la partie que tu as modifiée ralenti le programme
résultat:
avec tes 3 premières lignes modifiées:


def E_Crible(premiers, n, fam):
    # On génère un tableau de n//30 cases rempli de 1
    lencrible = n//30
    crible = [1 for _  in range(lencrible)]    
 

=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ Era_gty_mod30.py ===
Donnez N: 3000000000
nombre premier criblé de 7 à n pour la Fam = 18056145
--- Temps total: 18.9 sec ---

>>>
au lieu de


def E_Crible(premiers, n, fam):
    start_crible = time()
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)
 

=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ Era_gty_mod30.py ===
Donnez N: 3000000000
Nombre premiers criblés famille 7 : 18056145 ----- 14.35
--- Temps total: 14.53 sec ---
>>>

@+

Dernière modification par LEG (14-02-2020 14:50:04)

Hors ligne

#2 14-02-2020 12:08:21

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

Re : Fusion de deux cribles

Salut,

Ce que tu me présentes là, c'est le résultat de ta fusion des 2 prog, c'est bien ça ?

Je prends ta fonction épurée de tout ce que tu dis ne plus servir à rien suivie de def main()


def E_Crible(premiers, n, fam):
    # On génère un tableau de n//30 cases rempli de 1
    lencrible = n//30
    crible = [1 for _  in range(lencrible)]    
    GM = [7,11,13,17,19,23,29,31]
   
    # On calcule les produits: j = a * b
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  #Pour cribler directement à partir de l'index calculé
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0

def main():
    n = demander_n ()
    premiers = eratostene(n)
    start_time = time()
    E_Crible(premiers, n, 7)
    temps = time()-start_time

Je vais faire 3 remarques.
1.  E_Crible(premiers, n, 7)
    Tu appelles E_crible : ok... mais tu ne récupères aucun résultat.
    Ce n'est normal que si tout se passe dans E_Crible qui est alors la tour de contrôle.

2. Ce morceau me paraît avoir un problème d'indentation.

    # On calcule les produits: j = a * b
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  #Pour cribler directement à partir de l'index calculé
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0

    Je traduis en français :
     Pour chaque nombre premier a de la liste premiers :
           Pour chaque nombre b des 8 familles GM :
                 j = a* b
                 Si le reste de la division euclidienne de j par 30 est égal à fam :
     
    Commentaire : fam a été passé en paramètre (7 dans ton exemple) depuis la fonction main().
    Questions : l'utilisateur doit choisir la famille à étudier en modifiant ce 7 et en rentrant dans le programme ?
                     Tu ne passes donc pas en revue une famille après l'autre automatiquement...
                     Alors, pourquoi lui demander de rentrer n et pas également fam ?

Bon, jusque-là : broutilles...

Par contre, je reprends :
     Pour chaque nombre premier a de la liste premiers :
     |    Pour chaque nombre b des 8 familles GM :
     |    |    j = a* b
     |    |    Si le reste de la division euclidienne de j par 30 est égal à fam :
     |    |    |    index = j//30
     |    Pour idx allant de index à lencrible par pas de a :

Là, l'indentation me pose me pose problème :
Pour un nombre premier a donné, tu passes en revue tous les b de [7,11,13,17,19,23,29,31]
Pour chaque b, tu calcules j et si j%30== fam alors tu calcules l'index.
Et tu n'utilise cet index que lorsque tu as passé en revue tous les b, ce qui veut dire que seul le dernier b utilisé soit 31 aura servi à quelque chose. Ce qui est écrit est équivalent à :
     Pour chaque nombre premier a de la liste premiers :
     |    b=31
     |    j = a* b
     |    Si le reste de la division euclidienne de j par 30 est égal à fam :
     |    |    index = j//30
     |    Pour idx allant de index à lencrible par pas de a :

1er point.

Deuxième point.
je choisis la famille fam=23
Imaginons que a  = 983
j=983*31 = 30473
j%30 = 23
index=1015
Et donc tu boucles de 1015 à finboucle par pas de 983, soit les nombres
1015, 1998, 2981, 3964, 4947, 5930... jusqu'à finboucle
Normal ?
Moi je pensais qu'on ne rentrait dans la boucle que si j%30 == fam...
Là, avec cette indentation, que j%30== fam ou pas, que l'on ait calculé l'index ou pas on rentre dans la boucle :
Si j%30 $\neq$ fam alors :
- dans le meilleur des cas, on rentre dans la boucle avec le dernier index utilisé : calculs déjà faits
- au pire avec aucune valeur attribuée à index --> et paf, plantage !
Alors ? Réactions ?

@+


Arx Tarpeia Capitoli proxima...

En ligne

#3 14-02-2020 12:45:34

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

Re : Fusion de deux cribles

Re @Yoshi
Mais c'est les deux programmes que tu as fait...donc ? l'indentation est bonne..
mais le programme que j'ai mis c'est uniquement Ératosthène . je vais les reposer à la suite :
1-) Ératosthène  = E_Crible


from itertools import product
from time import time
from os import system
import math

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however


def eratostene(n):
    n = int(n**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_list =[2,3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])
    return prime_list[3:]  


def demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    #n = int(30 * round(float(n)/30))
    return n


def E_Crible(premiers, n, fam):
    start_crible = time()
 
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits: j = a * b
   
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0
        #print(index)
           
    total = sum(crible)  ##fonction qui sera inutile et remplacé par : return "crible:", crible ##
    print("crible:", crible)  
    print(f"Nombre premiers criblés famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")


def main():
    # On demande N a l'utilisateur
    n = demander_N()

    # On récupère les premiers de 7 à √N
    premiers = eratostene(n)
    #print(f"nombres premiers entre 7 et n: {len(premiers)}")

    start_time = time()
    # On crible
    E_Crible(premiers, n, 7)
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")


main()
system("pause")
 

2-) Goldbach = GCrible


from time import time
from os import system
import math

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however


def eratostene(n):
    n = int((2*n)**0.5)
    prime_list = [2, 3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])
    return prime_list[3:]


def demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    #n = int(30 * round(float(n)/30))
    return n


def GCrible(premiers, n, fam):
    start_crible = time()
    crible = n//30*[1]     # # Ou: on rappelle le tableau de E_crible,  criblé ##
    lencrible = len(crible)

    # On calcule les restes: ri = 2*n/pi
    nbpremiers = len(premiers)
    n2 = 2*n
 
    for i, premier in enumerate(premiers):
        reste = n2 % premier
        #print(reste)
  # tant que ri % 30 != fam on fait ri += 2pi
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise ri par 30 pour obtenir l'indexe
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0

    total = sum(crible)  
    print("crible:", crible)
    print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {total} ----- {int((time()-start_crible)*100)/100}")


def main():
    # On demande N a l'utilisateur
    n = demander_N()

    # On récupère les premiers entre 7 et √2N
    premiers = eratostene(n)
    #lprint("premiers:", premiers)
    #print(f"nombres premiers entre 7 et {int((2*n)**0.5)}: {len(premiers)}")

    start_time = time()
    # On crible
    GCrible(premiers, n, 7)
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")


main()
system("pause")
 

et Maintenant  voila les deux fusionné  mais qui ne fonctionne que sous le principe de Golbach , il ne prend pas le tableau d'Ératosthène criblé , parce que effectivement je ne sais pas comment il faut l'appeler ..... au niveau de la fonction :

 
def GCrible(premiers, n, fam):
    start_crible = time()
    crible = n//30*[1]     ## Ou: on rappelle le tableau Ératosthène criblé de N/30 cases, de E_Crible
    lencrible = len(crible)
 

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

3-) crible couple P+Q = GCrible_2N; celui que l'on doit modifier


from itertools import product
from time import time
from os import system
import math

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however


def eratostene(n):
    n = int((2*n)**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_list =[2,3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])
    return prime_list[3:]  


def demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    #n = int(30 * round(float(n)/30))
    return n


def E_Crible(premiers, n, fam):
    start_crible = time()
 
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits: j = a * b
   
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0
        #print(index)
           
    #total = sum(crible)  ### cette fonction devient inutile ###
    print("crible:", crible)  
    #print(f"Nombre premiers criblés famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")
    return "crible:", crible
 ################################# il faudrait fusionner à partir de là ########
def main():
    # On demande N a l'utilisateur
    n = demander_N()

    # On récupère les premiers de 7 à √N
    premiers = eratostene(n)
    #print(f"nombres premiers entre 7 et n: {len(premiers)}")

    start_time = time()
    # On crible
    E_Crible(premiers, n, 7)
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")
   
 ############### Goldbach. GCrible ##########
   
def GCrible_2N(premiers, n, fam):
    start_crible = time()
    crible = n//30*[1]     # Ou: on rapelle le tableau Ératosthène criblé de N/30 cases
    lencrible = len(crible)

    # On calcule les restes: ri = 2*n/pi
    nbpremiers = len(premiers)
    n2 = 2*n
 
    for i, premier in enumerate(premiers):
        reste = n2 % premier
        #print(reste)
  # tant que ri % 30 != fam on fait ri += 2pi
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise ri par 30 pour obtenir l'indexe
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0

    total = sum(crible)  
    print("crible:", crible)
    print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {total} ----- {int((time()-start_crible)*100)/100}")


def main():
    # On demande N a l'utilisateur
    n = demander_N()

    # On récupère les premiers entre 7 et √2N
    premiers = eratostene(n)
    #lprint("premiers:", premiers)
    #print(f"nombres premiers entre 7 et {int((2*n)**0.5)}: {len(premiers)}")

    start_time = time()
    # On crible
    GCrible_2N(premiers, n, 7)
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")


main()
system("pause")
 

Dans ce crible il n'y a que la fonction Goldbach qui crible , sans utiliser le tableau criblé de E_crible...

ensuite on pourra discuter des questions que tu as posé .., concernant E_crible , où si besoins est ....

citation: et réponses

Commentaire : fam a été passé en paramètre (7 dans ton exemple) depuis la fonction main().
    Questions : l'utilisateur doit choisir la famille à étudier en modifiant ce 7 et en rentrant dans le programme ? oui
                     Tu ne passes donc pas en revue une famille après l'autre automatiquement...pas du tout on travaille que par famille
                     Alors, pourquoi lui demander de rentrer n et pas également fam ? Bien sûr, mais on avait dit que c'était tout aussi facile de rentrer la fam avant de lancer le programme

par famille = gain de temps et de mémoire...!

citation: et réponses

Et donc tu boucles de 1015 à finboucle par pas de 983, soit les nombres
1015, 1998, 2981, 3964, 4947, 5930... jusqu'à finboucle ...# pas tout à fais , car 1015 est l'index et non un entier de la fam
Normal ? ..Bien sûr, ce sont les a = 983 dans ton exemple qui crible c'est à dire: on crible en partant de l'index modulo (a*30) puisque la fam est en progression arithmétique de raison 30
Moi je pensais qu'on ne rentrait dans la boucle que si j%30 == fam...
Non pas du tout chaque (a) vérifie que le produit j est bien égal à j%30==fam, puis on calcule son index et (a) part cribler; ensuite on réitère avec le (a) suivant

mais je pense que c'est par ce que tu ne t'en souviens plus, car c'est bien toi qui avais modifié le programme de mon petit fils pour l'optimiser  d'ailleurs tu pourrais revoir le sujet aide en python...mais inutile...

par exemple dans ta question pour a = 983, ok, l'index est 1015 ,ok cela correspond au nombre 1015*30 + 23 = 30473 = 31 × 983 les nombres seront donc :
en partant de 30473 ayant pour index 1015 dans la fam 23; 30473 +29490 +29490 +29490 ... etc ....> fin de boucle limite N//30  c'est bon...?

Exemple que cela devrait donner pour le criblage de E_crible par GCrible :
  pour N = 900 ; et fam = 7; (7couples) ; fonction : (20/ln40) = 5,42

1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1
0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0
résultat de GCrible_2N il ne marque que les 1, de E_crible corespondant au 1 de GCrible
0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0

Dernière modification par LEG (14-02-2020 13:44:49)

Hors ligne

#4 14-02-2020 15:44:21

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

Re : Fusion de deux cribles

Salut

Ton E_crible :

def E_Crible(premiers, n, fam):
    start_crible = time()
 
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits: j = a * b
   
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
        for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
            crible[idx] = 0
        #print(index)
           
    total = sum(crible)  ##fonction qui sera inutile et remplacé par : return "crible:", crible ##
    print("crible:", crible)  
    print(f"Nombre premiers criblés famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")


Ma dernière version fonctionnelle sans tripatouillage de décalage de bits en binaire présente sur ma machine et parfaitement fonctionnelle :

def E_CribleG3Y_mod30(n,fam):
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n)
    nbcell = n//30
    nombres = []
    GM = [7,11,13,17,19,23,29,31]
    for i in range(1):
        nombres.append([1]*nbcell)                
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)
   
    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    #print (Primes_init)
    print()
    for a in Primes_init:
        for b in GM:
            j = a*b
            if j%30 == 1:              
                debut_index = j//30
                Nombres_fam = nombres[fam]
                for index in range(debut_index, nbcell,pi):
                    Nombres_fam[index] = 0
    s_23=time()-start_time

    # CALCUL DES NOMRES PREMIERS de 7 à n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total += sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print(nombres)
    print("Extraction des premiers de 7 à n : %s seconds ---" % s_4)
    return total,s

Donc, non, ce que tu me présentes n'est pas ce que j'ai fait, c'est interprétation de ce que j'ai fait...
Moi :
Pour chaque a de premiers:
       Pour chaque b de GM:
            les deux progs calculent j=a*b
            Si j%30==fam:
                  calcul de l'index index = j//30
                  Pour idx de index à finboucle, pas =a

Toi :
Pour chaque a de premiers
       Pour chaque b de GM:
            les deux progs calculent j=a*b
            Si j%30==fam:
                  calcul de l'index index = j//30
            Pour idx de index à finboucle, pas =a

Tu ne vois pas de différence ? Vraiment ? alors tu m'as lu en diagonale...

Il fallait me dire que les 2 séparés fonctionnaient correctement et m'expliquer pourquoi cette indentation différente pas me dire que ce ne pouvait qu'être correct parce que c'était mon œuvre ce qui n'est pas exact.

Bon maintenant, j'ai sous la main et fonctionnelles deux prog où schématiquement :
main() versionE
      - appelle Erato
      - puis passe le résultat à E
      - qui crible et retourne la liste crible

main() versionG
      - appelle Erato
      - puis passe le résultat à G
      - qui crible et retourne la liste crible

que veux-tu ?
Une version où main()
      - appelle Erato qui renvoie prime_list
      - puis passe le résultat à E sous le nom de premiers
      - qui crible et retourne la liste crible
      - liste récupérée par main() qui la passe à G qui recrible ???
    autre chose ?

Je vais d'abord voir ta réponse, simple et courte si possible,
Fusionner selon tes vœux
Ensuite quand je jugerai que ça doit être correctement fusionné, je testerai
Et me repencherai sur cette histoire d'indentation ; je ne vois toujours pas pourquoi la boucle Pour idx ne démarre pas à chaque fois que le test if j%30== fam mais seulement quand tu as épuisé tous les b...

@+

Dernière modification par yoshi (14-02-2020 17:12:05)


Arx Tarpeia Capitoli proxima...

En ligne

#5 14-02-2020 17:03:06

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

Re : Fusion de deux cribles

Ok :
donc je vais commencer par cette question, qui effectivement ne devrait pas se produire , mais là je ne sais pas pourquoi , Car tu as raison l'instruction devrait être des-que J=(a*b ) et que j%30 ==fam, la fonction doit passer au calcul de l'index puis a part cribler..... est ce à ce niveau que ça tourne jusqu'à la fin des b de GM

je ne vois toujours pas pourquoi la boucle Pour idx ne démarre pas à chaque fois que le test if j%30== fam mais seulement quand tu as épuisé tous les b...Mais je crois que tu avais regardé et dans la version que de E_crible que j'ai mise, il calcule tous les b et ne prend que  j%30== fam avant de calculer l'index puis part cribler

il faut peut être que tu utilises la fonction que tu avais utilisé :

début, fin = a*b , j*%30==fam
for j in range(debut,fin):
    calcul de l'index index = j//30

puis :

Toi :
Pour chaque a de premiers
       Pour chaque b de GM:
            les deux progs calculent j=a*b
            Si j%30==fam:
                  calcul de l'index index = j//30
            Pour idx de index à finboucle, pas =a je suis d'accord que l'indentation n'est pas bonne, mais ça vient d'un ancien programme car je ne l'ai plus cette indentation ...ni l'utilisation de:

Nombres_fam = nombres[fam]
                for index in range(debut_index, nbcell,pi):
                    Nombres_fam[index] = 0

Il fallait me dire que les 2 séparés fonctionnaient correctement et m'expliquer pourquoi cette indentation différente pas me dire que ce ne pouvait qu'être correct parce que c'était mon œuvre ce qui n'est pas exact. Ok il y a erreur ...je pensais que tu le savais

Bon maintenant, j'ai sous la main et fonctionnelles deux prog où schématiquement :
main() versionE
      - appelle Erato
      - puis passe le résultat à E
      - qui crible et retourne la liste crible

Tout à fait

main() versionG
      - appelle Erato
      - puis passe le résultat à G
      - qui crible et retourne la liste crible

Tout à fait

*****************************************
que veux-tu ?
Une version où main()
      - appelle Erato
      - puis passe le résultat à E
      - qui crible et retourne la liste crible
      - liste récupérée par main() qui la passe à G qui recrible ???   ### c'est Exactement ça.. ###

en exemple la liste crible de E retourné et récupérée par main() pour la passer à G, cela va permette à G de ne pas  effectué le tableau de n//30 *[1]
et de cribler directement cette liste E criblée = tableau.

Donc pour résumer :
Exemple que cela devrait donner pour la liste E_crible, récuperé par main()pour la passer à GCrible_2N:
  pour N = 900 ; et fam = 7; (7couples (p+q))

1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1 ## liste E ##

résultat de GCrible_2N """ principe de base : il ne marque que les 1, de E_crible corespondant au 1 de GCrible"""
0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 

les deux cribles fonctionnels E_crible et GCrible permettront de vérifier que GCrible_2N à bien exécuté son programme de criblage identique à GCrible qui est le même bien entendu....

Dernière modification par LEG (15-02-2020 07:53:34)

Hors ligne

#6 14-02-2020 18:45:03

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

Re : Fusion de deux cribles

Salut,

Pas testé.
Je remets l'indentation correcte dans E et je fusionne :


from time import time
from os import system

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n = int(n**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_list =[2,3]
    sieve_list = [True for _ in range(n+1)] # c'est plus propre comme ça
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    #print(prime_list[3:])
    return prime_list[3:]  

def E_Crible(premiers, n, fam):
    # On génère un tableau de N/30 cases rempli de 1
    lencrible = n//30
    crible=[1 for _ in range(lencrible)] # c'est plus propre comme ça
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits :
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
                for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
                    crible[idx] = 0        
    return crible,lencrible
 
def GCrible_2N(premiers, crible, lencrible, n, fam):
    start_crible = time()
    # On calcule les restes: ri = 2*n/pi
    nbpremiers = len(premiers)
    n2 = 2*n
    for premier in premiers:
        reste = n2 % premier
        #print(reste)
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
       # tant que reste % 30 != fam on fait reste += pi2
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise reste par 30 pour obtenir l'index
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0

    total = sum(crible)  
    print("crible:", crible)
    print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {total} ----- {int((time()-start_crible)*100)/100}")

def demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    #n = int(30 * round(float(n)/30))
    return n

def main():
    # On demande N a l'utilisateur
    n = demander_N()
    # On récupère les premiers de 7 à √N
    premiers = eratostene(n)
    start_time = time()
    # On crible
    fam=7 # ou 11, 13, 17, 19, 23, 29, 31 au choix
    crible,lencrible=E_Crible(premiers, n, fam)
    GCrible_2N(premiers, crible, lencrible, n, fam)
   
main()
system("pause")

main() commence de la même façon
- appel erato qui retourne prime_list
- récupération de prime_list sous le nom de premiers
- appel de E en lui passant premiers, n, fam et qui retourne crible et lencrible que je récupère dans la foulée
- premiers, crible, lencrible, n, fam sont passés en paramètres à G (1ere ligne def G modifiée pour recevoir ces paramètres dans l'ordre)

J'ai une inconnue sur le fonctionnement, cette ligne :
n = int(n**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
Parce que G n'appelle pas erato pour créer des premiers, ils lui sont passés en paramètres (les mêmes que E a reçu en paramètres).

C'est ça qui risque de coincer, parce que la def main() modifiée répond bien à ce cahier des charges :
main()
      - appelle Erato qui renvoie prime_list
      - puis passe le résultat à E sous le nom de premiers
      - qui crible et retourne la liste crible
      - liste récupérée par main() qui la passe à G qui recrible ???

Mais comme je ne sais pas pourquoi tu as écris cela, je ne peux rien faire de plus pour l'instant.

A toi de jouer (tu connais ta bête), tu devrais être à même de pointer les pbs...
Ce qui serait encore mieux, quand cette version tournera, ce serait de fusionner les deux def E et G (en une seule) l'une après l'autre, ce qui éviterait de récupérer les données de E pour les les passer à G, puisqu'elles auraient fusionné (= les deux enchaînées l'un après l'autre avec des ajustements mineurs et cosmétiques...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#7 14-02-2020 19:10:57

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

Re : Fusion de deux cribles

J'ai une inconnue sur le fonctionnement, cette ligne :
n = int(n**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.

Tout à fait je l'ai directement passé dans E , au début d'Ératosthène à  n=int((2n)**0.5) cela ne prends pas plus de temps pour E, j'ai vérifié sur 3 000 000 000
avec n = int(n**0.5) ou n = int((2*n)**0.5)
mais il le faut pour G

je viens de tester , c'est impeccable , avec n = int((2*n)**0.5)
résultat:
Donnez N: 3000
crible: [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
Nombres non congru 2n[pi] 1 à 3000 famille 7 couple p+q = 2N: 18 ----- 0.01 il va pratiquement aussi vite que E tout seul ou G tout seul..

voici les données des deux fonctions E et G séparées on a bien 18 couples et les 1 du cribles GCrible_2N sont bien en correspondance avec les 1 de E et les 0 correspondent bien aux 0 de E ou de G .
j'ai mis en rouge je début des entiers de la liste E.... ce qui te permet de voir que les 0 de E qui sont marqué en noir ce sont des entiers non congrus à 2N [Pi] qui se décaleront d'un rang et si  il précède un 1 marqué en rouge, et bien ce 1 ne serra plus congru pour n=15(k+1) et donc vérifiera la conjecture car ce serra un couple p+q = 2N ....etc etc..C'est pour cela que ces 0 marqué en noir donc non congru ont tout autant d'importance que les 1 premiers non congrus...Mais ça , aucune analyse mathématique ou complexe ne pouvait le prévoir sans ces deux fonctions...car inconnues !

1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0

0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1
N = 3000 ; (18couples) ; fonction : (55/ln110) = 11,94.

superposé on doit garder que les 1 correspondant aux 1 tous les autres restent marqué 0

Ce qui te donne bien ton résultat :

0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0

Ce qui serait encore mieux, quand cette version tournera, ce serait de fusionner les deux def E et G (en une seule) l'une après l'autre, ce qui éviterait de récupérer les données de E pour les les passer à G, puisqu'elles auraient fusionné (= les deux enchaînées l'un après l'autre avec des ajustements mineurs et cosmétiques...

Ca c'est toi le chef de cette partie et tu as parfaitement raison ; rassure toi ça fonctionne et ça tourne bien...Il faut que je te paye le restau chez toi....

@+ je vais vérifier 3 000 000 000 . et je pourrai ensuite demander à B Parisse si il veut bien avoir la gentillesse de le retranscrire en C++ , comme il l'a fait pour les deux cribles...
sur un grand ordinateur on pourra allègrement repousser les limites où la "conjecture" à été testé , sans compter que l'on a besoin que d'une famille ....La je pense que personne ne pouvait l'imaginer...!

Dernière modification par LEG (14-02-2020 19:56:25)

Hors ligne

#8 14-02-2020 19:52:10

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

Re : Fusion de deux cribles

Re,

Alors dans ce cas, il va falloir expliciter tes deux réponses :
Numéro 1

- liste récupérée par main() qui la passe à G qui recrible ???   ### c'est Exactement ça.. ###

et
Numéro 2

Tout à fait je l'ai directement passé dans E , au début d'Ératosthène à  n=int((2n)**0.5) cela ne prends pas plus de temps pour E, j'ai vérifié sur 3 000 000 000
avec n = int(n**0.5) ou n = int((2*n)**0.5)
mais il le faut pour G

D'où questions :
G démarre bien avec le crible retourné par E puis le modifie  ?
Si G se sert de n=int(sqrt(2n)), puisque dans G il est écrit :

    crible = n//30*[1]     # Ou: on rappelle le tableau Ératosthène criblé de N/30 cases
    lencrible = len(crible)

alors le crible ainsi construit ne contiendra pas le même nombre d'éléments que celui de E.
En effet, je vais suivre n à la piste.
Supposons :
Dans main()
-appel de demande(n), je réponds 1200
cf :

n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))

il n'est pas question de = int(n**0.5)
le n passé à E étant 1200, E va utiliser un crible de 1200//30 = 40 éléments
Or G d'après ce que tu dis est prévu pour traiter un crible de
int((2*n)**0.5))//30 = 48//30 = 1 élément...
Là, j'ai comme un problème...

Je ne vois pas de solution dans ces conditions, puisque E et G ne servent pas du même n, pour que le 2e utilise le crible du 1er...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#9 14-02-2020 20:55:50

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

Re : Fusion de deux cribles

Ok : mais d'abord un résultat de ta version qui fonctionne parfaitement et qui est juste..!

== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ couple p+q_mod30.py ==
Donnez N: 6 000 000 000
Nombres non congru 2n[pi] ou nombre de couple p+q = 2n, 7 à 6000000000 famille 7 : 5370017 ----- 29.48 ce temps il faut le multiplier par 2 ..bref on s'en fou
>>>

tout au début on a besoin des nombres premiers d'Ératosthène pour le crible E et pour le crible G donc comme pour la fonction GCrible il nous faut impérativement les nombres premiers $\leqslant\sqrt{2n}$ alors que pour la fonction Ecrible on a besoins que des nombres premiers $\leqslant\sqrt{n}$

J'ai donc vérifié, si cela ralentissait la fonction Ecrible si on rentrait n = in((2*n)**.5)  ce qui ne gène en rien ..et comme ça on rentrait directement tous les premiers d'Ératosthène que l'on va avoir besoins pour la fonction GCrible sans que cela gène Ecrible....OK

Alors tu vas me dire que les nombres premiers $\geqslant\sqrt{n}$ ils ne servent à rien dans la fonction Ecrible et ils tournent inutilement...oui ! mais coûtent très peu en temps ....j'avais penser te le demander, de ne retourner dans la première partie que les nombres premiers

 return prime_list[3:] et  ⩽√n

mais comme ça risquait de compliquer le programme j'ai donc opté pour la solution la plus simple en ne rentrant qu'une fois  n = in((2*n)**.5) pour les deux fonctions E et G.

Or lorsque l'on demande n = 1200 dans ta question:
on a besoin au maximum pour "eratostene" uniquement de rentrer n = int((2*n)**0.5) afin qu'il retourne les nombres premiers que l'on aura besoins dans les deux cas  donc le maximum .... pour la fonction G
(n'oublie pas qu'au tout début des programmes dans "eratostene" on calculait tous les nombres premiers pour rien, car on avait au maximum: besoin que des premiers $\leqslant\sqrt{2n}$)

il ne faut pas confondre cette première partie "eratostene" avec les deux autres E et G qui n'ont rien à voir, si ce n'est qu'il leur faut cette première partie pour fonctionner...!

Bien évidemment que tu vas appeler pour E les premiers d'Ératosthène pour cribler la liste E  et alors ...ça ne gène en rien d'en avoir un peu plus car ça ne peut en aucun cas changer le résultat de E...donc la liste E. Tu peux essayer avec les programme de E tout seul en entrant n=in((2*n)**0.5)

G , à besoin des premiers "eratostene" $\leqslant\sqrt{2n}$ pour cribler les éléments de la liste E criblée  qui ne sont pas les même éléments que "eratostene ...c'est ce qui t'embrouille...

sinon le crible serait faux il ne fonctionnerait pas.

Je ne vois pas de solution dans ces conditions, puisque E et G ne se servent pas du même n, pour que le 2e utilise le crible du 1er... si mais c'est deux choses différentes le $n$ rentré au début permet d'écrire deux tableaux identiques de cellules [1] n//30 , ok  mais ils utiliseront donc les mêmes nombres premiers $\leqslant\sqrt{2n}$ d'eratostene extraient dans les deux cas, pour cribler. Si ce n'est que les nombres premiers $P_i >\sqrt{n}$ dans E ne serviront à rien...ok...!

d'ailleurs voila un extrait de GCrible _2N, pour n= 3000

== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ couple p+q_mod30.py ==
Donnez N: 3000

[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73] nombres premiers extrait par eratosthène

résultat du nombre de couples p+q=6000

Nombres non congru 2n[pi] ou nombre de couple p+q = 2n, 7 à 3000 famille 7 : 18 ----- 0.0
>>>
pour E ça ne gène en rien mais par contre si je rentrer n=in(n**0.5) il est clair que le résultat serait faux !!! car il manquerait pour G les nombres premiers d'eratostene[ 59, 61, 67, 71, 73] car $\sqrt{3000}= 54$ alors qu'il me faut les $P_i\leqslant\sqrt{6000}= 77$

Et fonction G fausse : résultat :
[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
résultat faux
Extrait : Nombres non congru 2n[pi] ou nombre de couple p+q = 2n, 7 à 3000 famille 7 : 21 ----- 0.0seconde . Ce qui est faux, puisqu'il me manque des nombres premiers pour cribler, donc résultat en hausse....OK

Une dernière pour te rassurer:

== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ couple p+q_mod30.py ==

Donnez N: 9000

[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131] premiers "eratostene"

Gcrible_2N: [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Nombres non congrus 2n[pi] ou couples p+q = 2N 7 à 9000 famille 7 : 48 ----- 0.03 * 2
>>>
Résultat par la fonction d'estimation $\frac{\pi(n)} {ln\:2*\pi(n)}$
où $\pi(n)$ dans cette famille 7[30] et pour n= 9000 : Nombre de premiers liste E criblés : 141 , ce qui donne :

$\frac{141}{ln\:282}=24$ < 48 .

Dernière modification par LEG (15-02-2020 08:33:02)

Hors ligne

#10 14-02-2020 21:08:55

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

Re : Fusion de deux cribles

B'soir,

Bon si la fusion a réussi du premier coup, c'est bien.
Donc je vais passer dès demain à la suite proposée :
une seule fonction
def criblage_double(premiers,n, fam):

on devrait gagner temps et charge mémoire, je pense :
si on joue avec 1000 nombres retourner ce tableau, le récupérer  et le retransmettre
ou créer un crible de nombres pour enchaîner immédiatement sur 2e criblage, ne change pas grand chose.
Mais jouer avec 3 000 000 000 implique un facteur multiplicatif de 3 000 000 ne doit pas être anodin.
Vu que tel que fait ce soir ça roule, demain pour la fusion réelle, ça devrait prendre 5 min...

Même si l'idée ne te bottait pas plus que ça, je le ferai quand même pour ma satisfaction personnelle.

Quant à ta suggestion :

return prime_list[3:] et  ⩽√n

voilà :

return prime_list[3:int(n**0.5)]

Et je pencherai plus avant sur ta réponse concernant n ou 2n...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#11 14-02-2020 21:41:39

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

Re : Fusion de deux cribles

Bien entendu @Yoshi
mais le problème c'est que si on

return prime_list[3:int(n**0.5)]

ça ne marchera que pour E_crible et faussera le résultat de GCrible _2n

donc c'est à l'appelle de

def E_Crible(premiers, n, fam):

c'est ici qu'il faut appeler les premiers $\leqslant\sqrt{n}$ d'ératosthène il faudra dans main() par exemple rentrer : prime = eratosthène(n**0.5) et appeler dans la fonction ci-dessus :  prime,n,fam):

mais ça ne marche pas je viens d'essayer, j'ai remplacé premiers par prime, de partout où def de la liste E était utilisait... Par ce que je fais des erreurs dans python...

il faut que j'aille manger un bout ...bonne nuit A demain
Merci de ton dévouement.....
@+

Même si l'idée ne te bottait pas plus que ça, je le ferai quand même pour ma satisfaction personnelle...non , je pense que je me suis mal exprimé si tu le fais ce ne serra que mieux...et plus rapide...déjà si on évite pour liste E d'utiliser les primes "eratostene" $\geqslant\sqrt{n}$

actuellement pour n = 6000 000 000 il met 61 secondes ; alors que séparé , les deux fonction E et G mettent au total 59,64 secondes donc tu vois 1 seconde d'écart....Ce qui est logique, car le temps de chaque criblage ne peut pas diminuer du seul fait de la fusion des deux listes...

j'ai quand même fait une vérife : pour N = 7*1012 avec 2N = 14*1012 dans la liste E il y aura plus de 1 100 000 nombres premiers $P_i$ qui calculeront pour rien....Donc...si on peut épurer ce cas....

Dernière modification par LEG (15-02-2020 08:57:57)

Hors ligne

#12 15-02-2020 12:44:22

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

Re : Fusion de deux cribles

Salut,

Si j'ai bien compris, pour un $n$ donné
- le E_crible tourne avec les premiers $\leqslant \sqrt n$
- le G_crible, lui, doit impérativement tourner avec les premiers $\leqslant \sqrt{2n}$ ?

Si c'est bien le cas, alors dans Eratostene, je me proposais de générer
- les premiers $\leqslant \sqrt{2n}$
- de les retourner sous forme deux listes :
  * une de 3 à $\sqrt n$ qui servira à la première partie, ce qui était le crible E
  * le complément de $\sqrt n$ à  $\sqrt{2n}$, qui lorsque la partie E aura terminé de cribler, sera ajouté à la suite de la première liste.
     Ainsi, elle contiendra donc les premiers de 3 à $\sqrt{2n}$ ce qui permettra d'enchaîner sur la partie G.

J'ai passé la matinée sur cette problématique, mais la première liste est bonne c'est la deuxième qui coince et je ne trouve pas pourquoi.
Tant que je démarre candidate curr=5, ok
Mais dès que je modifie le point de départ comme étant le dernier de la première liste, ou même à 7 je n'ai plus de nombres premiers...
C'est vraiment un mystère.
Sinon, la fusion sans séparation a bien été faite en 5 min...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#13 15-02-2020 14:15:36

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

Re : Fusion de deux cribles

Alors la, c'est deux restau.. que je te dois...l'idée est excellente ...

Si j'ai bien compris, pour un n donné
- le E_crible tourne avec les premiers ⩽√n ## oui ##
- le G_crible, lui, doit impérativement tourner avec les premiers ⩽√2n ? ## ou i##

* une de $3 \:à \:√n$ qui servira à la première partie, ce qui était le crible E ## exact ##

* le complément de $√n$ à  $√2n$, qui lorsque la partie E aura terminé de cribler, sera ajouté à la suite de la première liste.
     Ainsi, elle contiendra donc les premiers de $3\: à \:√2n$ ce qui permettra d'enchaîner sur la partie G. ## et ça ne gênera en rien le ralentissement de GCrible_2N, c'est impec...###

J'ai passé la matinée sur cette problématique, mais la première liste est bonne c'est la deuxième qui coince et je ne trouve pas pourquoi.
Tant que je démarre candidate curr=5, ok
Mais dès que je modifie le point de départ comme étant le dernier de la première liste, ou même à 7 je n'ai plus de nombres premiers...
C'est vraiment un mystère. ### tu veux parler de liste E et des  $8\: b¤ premiers de GM ..? ###

Tu ne te souviens plus qu'on en avait parlé, et je t'avais suggéré si on inversé , c'est à dire que c'est à $b$ de GM de parcourir les $a$ de premiers  "eratostene" et tu m'avais dit que cela ne changerait pas le nombre d'opérations....Et tu avais raison... en principe...

Car supposons que l'on ai 2000 $P_i$ "eratostene"  ok
je part avec $b_1 = 7$ qui parcourt les $a_1, a_2 ....a_n $ dès que $(j = b_i*a_i)$ %30 == fam, stop , index $a_i$ part cribler de l'index...>n//30 ; sort du crible, et $b_i$ continu de parcourir les $a_i$ puis à nouveau %30==fam ce $a_i \:+\:_n$ part cribler ....etc... lorsque $b_1 = 7$ a fini de pracourir tous les $a_i$ "eratostene" et bien on réitère avec $b_2 = 11$ ....etc on arrive au dernier $b_8 = 31$ qui fini sa boucle jusqu'au dernier $a_i$ et fin du crible liste E...tu es d'accord...?

Mais le nombre d'opérations serra quand même 8*2000 calculs , vérification du modulo30==fam ..à l'inverse
dans l'autre sens qui est celui actuel et ben on a : 2000 * 8.... sauf si effectivement on pouvait faire partir le $a_i$ dés que  $j\:=\:b_i\:*\:a_i$ %30==fam

alors que c'est vrai , pourquoi le calcul de l'index de ce $a_i$ ne se fait pas dés que j%30==fam...??? alors que tu le faisais dans le crible G4y

extrait du programme :


 for i,pi in enumerate(Primes_init):      
       j=nn%pi
       debut,fin,pas=j+pi*(1-j%2),min(pi*30,n),pi*2  ### là, dès que (j + pi)%30== fam on part calculer l'index de j pour qu'il crible par pas de pi  ###
       temoin=0
       for j in range(debut,fin,pas):
           if j%30==1:
             fam=P8[1]  # modifier la valeur de la fam à cribler [1,7,11,....,29]
             if not ((1<<fam)&temoin):
                temoin=(1<<fam)|temoin
                debut_index=j//30
                Nombres_fam=nombres[fam]
                for index in range(debut_index, nbcell,pi):
                   Nombres_fam[index]=0
 

d'ailleurs on avait imprimé tous les j pour être sûr que les opérations d'additions s'arrêtaient avant la limite bornée par (pi*30,n) dès que j%30==fam
et on avait en moyenne au grand maxi  si cela allait au bout de la limite: 16 additions et donc 16 contrôles modulo 30==fam...

cela vient peut être des deux fonctions for... qui ne peuvent être interrompues par while par exemple...il faudrait une instruction dans la processus de calcul de $b_i$...
j'ai même essayé en mettant dans la fonction for fin = j%30==fam


 for a in premiers:
        fin = j%30==fam
        for b in GM(fin):
 

nada qu'il m'a dit, retourne apprendre python tu as 00:
1, in E_Crible
    fin = j%30==fam
UnboundLocalError: local variable 'j' referenced before assignment

Dernière modification par LEG (15-02-2020 14:26:05)

Hors ligne

#14 15-02-2020 14:57:17

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

Re : Fusion de deux cribles

Re,


Nan.
Ca se passe dans le couple  def eratostene + def candidate range
Je voudrais couper en deux la construction de prime_list, je n'arrive pas à faire les modifs pour aller d'abord de 5 à int(n**0.5) puis reprendre
de int(n**0.5) à int((2*n)**0.5)...

@+
[EDIT]
J'ai (un peu) triché :
Essaie ça :

from time import time
from os import system

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n1,n = int(n**0.5), int((2*n)**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_E,prime_EG=[2,3],[]
    sieve_list = [True for _ in range(n+1)] # c'est plus propre comme ça)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            if each_number>n1:
                prime_EG.append(each_number)
            else:
                prime_E.append(each_number)
            for multiple in range(each_number*each_number, n, each_number):
                sieve_list[multiple] = False
    return prime_E[3:],prime_EG


def Criblage_EG(Premiers,Premiers_suite, n, fam):
    start_time = time()
    # On génère un tableau de n//30 cases rempli de 1
    lencrible = n//30
    crible=[1 for _ in range(lencrible)] # c'est plus propre comme ça
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits :
    for a in Premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
                for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
                    crible[idx] = 0
    Premiers+=Premiers_suite
    del Premiers_suite # suppression du tableau devenu inutile
    nbpremiers = len(Premiers)
    n2 = 2*n
    for premier in Premiers:
        reste = n2 % premier
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
       # tant que reste % 30 != fam on fait reste += pi2
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise reste par 30 pour obtenir l'index
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0
    total = sum(crible)  
    print("crible:", crible)
    print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {total} ----- {int((time()-start_crible)*100)/100}")

def demander_n():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    #n = int(30 * round(float(n)/30))
    return n

def main():
    # On demande n à l'utilisateur
    n = demander_n()
    # On récupère les premiers de 7 à √n et de √n à √2n
    Premiers_E,Suite_E = eratostene(n)
    # On crible
    fam = 7 # ou 11, 13, 17, 19, 23, 29, 31 au choix
    Criblage_EG(Premiers_E,Suite_E, n, fam)
   
main()
system("pause")

Dernière modification par yoshi (15-02-2020 16:56:10)


Arx Tarpeia Capitoli proxima...

En ligne

#15 15-02-2020 16:32:52

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

Re : Fusion de deux cribles

ça y est , je regardai le Biathlon.

donc je vais tester :  je vois que tu as modifié la def eratostene , afin de partager les listes de premiers

une erreur:
Criblage_EG(PremiersE,Suite_E, n, fam)
NameError: name 'Criblage_EG' is not defined
>>>

cette ligne: Crible_EG(Premiers_E,Suite_E, n, fam) comporte deux erreur Criblage_EG au lieu de Crible_EG et il manque le tiret du 8 à PremierE

résultat pour n= 300 :Donnez N: 300
crible: [1, 1, 0, 1, 0, 1, 0, 0, 0, 0]

avec GCrible_2N
crible: [1, 1, 0, 1, 0, 1, 0, 0, 0, 0] ; identique donc ok

je pousse N à 6000 Crible_EG
Donnez N: 6000
crible: [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0]
Nombres non congru 2n[pi] 1 à 6000 famille 7 premiers de 6000 à 12000: 46 ----- 0.03 on perd 2 dixièmes
GCrible_2N
Donnez N: 6000
crible: [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0]
Nombres non congru 2n[pi] ou couple p+q = 2N, de 7 à 6000 famille 7 : 46 ----- 0.01

résultat identique et valeurs bonnent

il ne reste que cette ligne à modifier car elle induit une erreur :
##print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {total} ----- {int((time()-start_crible)*100)/100}")

print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {total} ----- {int((time()-start_crible)*100)/100}")
NameError: name 'start_crible' is not defined

C'est fait , c'est sous la fonction def tu as mis : start_time au lieu de star_crible = time

je fais un test sur 6 000 000 000 on verra l'écart de temps ok.

Dernière modification par LEG (15-02-2020 17:06:51)

Hors ligne

#16 15-02-2020 16:45:31

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

Re : Fusion de deux cribles

Re,

Correction basique :
def Crible_EG --> def Criblage_EG

code corrigé...

@+

Dernière modification par yoshi (15-02-2020 16:55:47)


Arx Tarpeia Capitoli proxima...

En ligne

#17 15-02-2020 17:10:54

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

Re : Fusion de deux cribles

n'ouble pas le tiret du 8 à Premiers_E:(PremiersE,Suite_E, n, fam)

il y a un nombre en plus dans cette double liste : prime_E,prime_EG=[2,3],[]

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] [59, 61, 67, 71, 73, 77] 77 ne devrait pas y être...à priori il prend le dernier entier de la racine carrée de 2N , pour 2n =12000, il affiche aussi 109 là ok car 109 est premier

je pense pas que cela pose problème dans le processus , puisqu'un nombre composé ne peut rien marquer, qui ne serait marqué par ses facteur P....

premier résultat pour 6mds avec GCrible _2N

Nombres non congru 2n[pi] ou couple p+q = 2N, de 7 à 6000000000 famille 7 : 5370017 ----- 30.13 *2 environ

deuxième résultat pour 6 mds avec Crible _EG

Nombres non congru 2n[pi] 1 à 6000000000 famille 7 premiers de 6000000000 à 12000000000: 5370017 ----- 66.53

donc il fonctionne parfaitement...et c'est marrant car même avec moins de nombres premiers qui criblent liste E il ne va pas plus vite...
je viens de revérifier il gagne 12 secondes sur n =12 mds donc ça m'étonnez qu'il n'aille pas plus vite ..

maintenant je vais voir en C++..si je peut le faire retranscrire   et si oui je le publie sur le forum ...mais déjà cela ferait un bon exécutable sur vvotre site car ce programme et algorithme est totalement inconnu....

MON CHER AMI je te suis redevable tu ne veux pas aller au resto....? j(attend ton mail)....

Dernière modification par LEG (15-02-2020 17:52:22)

Hors ligne

#18 15-02-2020 18:25:47

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

Re : Fusion de deux cribles

Re,

il y a un nombre en plus dans cette double liste : prime_E,prime_EG=[2,3],[]

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] [59, 61, 67, 71, 73, 77] 77 ne devrait pas y être...

Pour quelle valeur de n ?
Il est possible que ce soit un bug du programme calcul erato ou candidate_range parce que ma seule intervention dans ces deux defs est la structure if else ajoutée pour la séparation.
Autre possibilité : le calcul à partir de $\sqrt{2n}$ introduit parfois un faux positif à la fin... Mais
1. Pourquoi à la fin ?
2. Pourquoi n'a-t-on rien vu avant ?
D'où la question : pour quelle valeur de n ?

Pour comparer les temps, l'ami tu ne peux pas comparer le temps de Criblage_EG  avec celui de G_crible. mais avec le temps E_crible + temps G_crible

@+


Arx Tarpeia Capitoli proxima...

En ligne

#19 15-02-2020 18:45:15

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

Re : Fusion de deux cribles

pour N = 3000
sqrtde 12000 = 77,....

N= 7335
sqrt 14760 = 121,...

en définitive il prend la dernière valeur impaire et entière de la racine carrée de 2N.
mais si entre le dernier premier est la valeur entière impaire de la sqrt de 2N il y a d'autres impairs non premiers il ne les prend pas ...dans l'exemple au dessus il y a 119 qui n'est pas premier , il ne l'a pas pris heureusement...il s'est arrêté à 113
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83] [89, 97, 101, 103, 107, 109, 113, 121]

je pense que cela vient du fait que l'on travaille modulo 30...Car dans un crible P[30] que j'ai , il arrive souvent que le dernier nombre avant la limite n fixé est un composé...! c'est exactement pareil que dans un des cribles que tu as programmé le dernier nombre premier se trouve en double....!
aucune importance c'est un bug, sans incidence...

pour les temps bien entendu c'est ce que j'ai comparé...au début , la je compare le temps de des deux cribles que tu viens de programmer et GCrible_2N met 8 seconde de moins pour N = 12 000 000 000 avec un chrono car il ne m'indique pas le temps pour la partie E , je n'ai pas réussi à le faire.....

voila pour era_gty , crible E
Nombre premiers criblés famille 7 : 67695482 ----- 62.32
--- Temps total: 63.03 sec ---
>>>
voila pour g_t_y , crible G
Nombres non congru 2n[pi] 1 à 12000000000 famille 7 premiers de 12000000000 à 24000000000: 63579248 ----- 63.27
--- Temps total: 64.03 sec ---

Dernière modification par LEG (15-02-2020 19:10:49)

Hors ligne

#20 15-02-2020 19:09:39

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

Re : Fusion de deux cribles

Re,

Que ce soit la version d'origine du couple erato + candidate_range ou la version retouchée avec if else ajouté
Pour n =3000, le dernier nombre est 73 chez moi pas 77.
Pour n =7335, le dernier nombre est 113 chez moi pas 121.

Où est la blague ?

@+


Arx Tarpeia Capitoli proxima...

En ligne

#21 15-02-2020 19:12:58

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

Re : Fusion de deux cribles

la blague vient de comment j'imprime :  # print(prime_E,prime_EG)   ça ne doit pas être bon....§ je vais l'enlever....

Dernière modification par LEG (15-02-2020 19:14:25)

Hors ligne

#22 15-02-2020 19:22:50

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

Re : Fusion de deux cribles

Ave,

Je ne vois pas pas pourquoi, je n'y crois pas une seule seconde...
1. Essaie seulement d'imprimer  comme : print(prime_EG[-1]) soit seulement le dernier nombre de prime_EG...
2. Si ça persiste (et ça devrait), remplace tes deux def par celles de mes essais (décalage d'indentation suite à copier/coller ? Je n'y crois pas non plus) :

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n1,n = int(n**0.5),int((2*n)**0.5)
    prime_E,prime_EG=[2, 3],[]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            if each_number > n1:
                prime_EG.append(each_number)
            else:
                prime_E.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    return prime_E[3:],prime_EG

3. On n'a pas la même version de Python : moi, 3.5.2  et toi, 3.7...
    J'ai un 3.2 qq part. je vais chercher où...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#23 15-02-2020 19:32:15

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

Re : Fusion de deux cribles

non il m'a mis 77 pour n=3000, donc 2n=12000
je colle les deux def.
ok c'est bon.....il m'a mis 124,73

par contre je n'arrive pas à calculer le temps dans ta première version d'hier pour :


def E_Crible(premiers, n, fam):
    # On génère un tableau de N/30 cases rempli de 1
    lencrible = n//30
    crible=[1 for _ in range(lencrible)] # c'est plus propre comme ça
    GM = [7,11,13,17,19,23,29,31]
    # On calcule les produits :
    for a in premiers:
        for b in GM:
            j = a * b
            if j%30 == fam:
                index = j // 30  # Je calcule l'index et On crible directement à partir de l'index
                for idx in range(index, lencrible, a):  # index qui est réutilisé ici...
                    crible[idx] = 0        
    return crible,lencrible

pour ensuite avoir le temps total de E et G afin de voir avec la dernière version....
 

Dernière modification par LEG (15-02-2020 19:41:59)

Hors ligne

#24 15-02-2020 19:36:39

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

Re : Fusion de deux cribles

Re, ouh là !!

non il m'a mis 77 pour n=3000, donc 2n=12000

a quoi tu joues ? tu le sors d'où ce 12000 ? chez moi 3000 * 2 = 6000 pas 12000...

ok c'est bon.....il m'a mis 124,333

??? 124,333 c'est quoi ?


Arx Tarpeia Capitoli proxima...

En ligne

#25 15-02-2020 19:40:04

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

Re : Fusion de deux cribles

non je rigolllllle   il indique bien 73 pour n=3000, soit 2n=6000

Hors ligne

Pied de page des forums