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

#26 22-01-2018 17:27:19

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

Re : crible en python

yoshi a écrit :

Re,

Attention si tu as remplacé ta fonction par la mienne (pas une bonne idée,  trop lente), il faut déjà que partout dans ton programme où il est écrit eratostene sans h, tu rajoutes le h...
Tu l'as bien fait ?

ok donc il faudrait que je remplace la première fonction d'eratostène sans h , par la tienne ci dessous

def eratosthene(n):
    nombres, premiers = [],[]
    for i in range(2,n+1):
        nombres.append(True)
    for i in range(2,n+1):
        if nombres[i-2]:
            premiers.append(i)
            for j in range(2*i,n+1,i):
                nombres[j-2] = False
    return premiers

n=1000
nn=int((2*n)**0.5)
premiers = eratosthene(n)
print(premiers)

et qu'ensuite je mette un h à ératosthène la où il n'y est pas y compris dans la parti crble_g ...?

Ah, ça travaille sous dos !!!
Alors dans ce cas, si tu as recopié mon prog, rajoute à la fin, le input() du tien. Relance et dis-moi si c'est ça...
Son rôle est d'empêcher - sous DOS - la fenêtre de se fermer : avec l'IDLE de Python sous Windows, c'est inutile, je l'avais supprimé
@+

si je copie ta fonction ci dessus, et pas la totalité de ton programme, il y a le input() à la fin du prog..

avec ta fonction je remplace toutes cette partie ? :

def eratostene (n):
  n = int(n)
  m = (n-1) // 2
  b = [True]*m
  i = 0
  p = 3
  premiers = [2]
  while p*p < n:
    if b[i]:
      premiers.append(p)
      j = 2*i*i + 6*i + 3
      while j < m:
        b[j] = False
        j = j + 2*i + 3
    i += 1
    p += 2
  while i < m:
    if b[i]:
      premiers.append(p)
    i += 1
    p += 2
  return premiers


def compteInfN(liste, n):
  compte = 0
  lenListe = len(liste)
  for i in range(0, lenListe):
    if (liste[i] >= n):
      compte += 1
  return compte

Hors ligne

#27 22-01-2018 17:42:09

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 302

Re : crible en python

Ave,

Quand c'est un programme pas destiné grand public, j'ai pris l'habitude de rentrer les valeurs nécessaires en "dur" et non pas via Input :
n = int(input("Donnez la valeur de N : ")).
Donc j'écris n=1000 ou 3000 ou 50 000 000 (sans espaces), ce que je veux...
Parce que sinon, pour être logique il faut essayer de prévoir toutes les erreurs d'ENTREE...

Sous windows, la fenêtre reste ouverte, sous DOS elle se ferme en fin d'appel.
Pour éviter cela, on ajoute qq ch qui fait que le prog attend... : ici le input(). Il y a encore d'autres astuces pour ça.

@+
Les deux fonctions peuvent parfaitement cohabiter dans le même programme.
Il aura le même fonctionnement que d'habitude.
Simplement, pour utiliser l'une ou l'autre fonction, il suffit d'écrire eratostene ou eratosthene partout...
Cela fait, tu enregistres.
Après, ainsi que je te l'ai dit, ça ne changera en rien ni tes habitudes, ni le fonctionnement.
Mais c'est inutile, ta fonction ou la mienne renvoient la même liste, et la tienne est 3 x plus rapide


Arx Tarpeia Capitoli proxima...

Hors ligne

#28 22-01-2018 18:16:18

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

Re : crible en python

Ok Yoshi
donc pour l'instant, je laisse en l'état, en attendant que je puisse modifier la première partie
def eratosthène , afin qu'il ne crible que jusqu'à la racine carrée de n lorsque l'on rentre la valeur de n. pour la fonction du crible_g dans le programme...

il faut je suppose remplacer la première partie du programme


import math

def eratostene (n):
  n = int(n)
  m = (n-1) // 2
  b = [True]*m
  i = 0
  p = 3
  premiers = [2]
  while p*p < n:
    if b[i]:
      premiers.append(p)
      j = 2*i*i + 6*i + 3
      while j < m:
        b[j] = False
        j = j + 2*i + 3
    i += 1
    p += 2
  while i < m:
    if b[i]:
      premiers.append(p)
    i += 1
    p += 2
  return premiers


def compteInfN(liste, n):
  compte = 0
  lenListe = len(liste)
  for i in range(0, lenListe):
    if (liste[i] >= n):
      compte += 1
  return compte


def premiersNa2N(n):
  #liste1 = eratostene(n*2)
  #compte = compteInfN(liste1, n)
  liste2 = crible_G(n)
  print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
  #print("> N / log(2N) = " + str(n / math.log(2 * n)))
  #print("> Pi(2N) = " + str(len(liste1)))
  print("> Estimation du TNP Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
  print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
  print("> Estimation Pi(2N)-Pi(N) = N/log(2N) = " + str(n / math.log(2*n)))
  #print("> Avec eratosthene: On compte " + str(len(liste1)-compte) + " nombres premiers entre 1 et " + str(n))
  #print("> Avec eratosthene: On compte " + str(compte) + " nombres premiers entre "+str(n)+" et " + str(n*2))
  print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
  # print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
  # print(liste2)
 

et ne garder que les quatre ligne


        print("> Estimation du TNP Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
  print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
  print("> Estimation Pi(2N)-Pi(N) = N/log(2N) = " + str(n / math.log(2*n)))
       print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
 

jusqu'à la deuxième partie, la fonction :
def crible_G(n):

...etc...




...etc

Hors ligne

#29 22-01-2018 18:36:19

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

Re : crible en python

c'est quand même beaucoup moins rapide que mon crible NB premier, qui lui pour crible de 1 à n et de 1 à 2n jusqu'à 1 000 000 000 il met 28 secondes alors que dans pycharm pour le crible_mod 30 , tu as vu le temps qu'il met jusqu'à 990 000 000 au dela il ne prend pas , je suppose que cela vient qu'il crible Eratosthène  jusqu'à n ou 2n, puis le crible_g jusquà n et le crible_mod 30 les 8 familles jusqu'à n

Le but de ce crible G ( en référence à Goldbach) c'est un outil identique à Eratosthène, qui implique la fonction du TNP pour une Lim n fixée
[tex]\frac{n} {Ln n}[/tex] d'ou on peut prouver que la fonction G(n) relatif au crible G, vaut [tex]\frac{n}{Ln 2n}[/tex] lorsque la lim n tends vers + l'infini...

Ce qui est vrai pour [tex]\pi(n)[/tex] et son crible Eratosthène est vrai pour [tex]G(n)[/tex] et son crible G : qui est Eratosthène dans les congruences mais avec le même principe...etc....etc.

Cette deuxième fonction [tex]\frac{n}{Ln 2n}[/tex] n'est autre, qu'un corollaire du TNP, grâce à cet outil de crible... il est vrai que dans le crible G on utilise les premiers [tex]P_i\leqslant\sqrt{2n}[/tex] au lieu de  [tex]P_i\leqslant\sqrt{n}[/tex] d'où la fonction 2 avec le (log n ) de 2n...

Hors ligne

#30 23-01-2018 13:41:41

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

Re : crible en python

Bonjour
@Yoshi : pourquoi au lieu de faire appel à Eratosthène , on ne rentre pas une base de données de nombres premier , par exemple [tex]\leqslant\sqrt{2000000000}[/tex] ce qui fait en gros 4400 nombres premiers [tex]P_i [/tex] que la fonction du crible_G va utiliser , en fonction de la valeur de n rentrée à la demande...? ce qui évite un criblage, puis stockage ....etc etc...

soit d'emblée dans le programme on inclue la base de données [tex]P_i [/tex] soit à la demande en fonction de n donc les [tex]P_i\leqslant\sqrt{2n}[/tex] ..... tout simplement....

Hors ligne

#31 26-01-2018 06:02:19

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

Re : crible en python

Bonjour

yoshi a écrit :

Ave,
@+
Les deux fonctions peuvent parfaitement cohabiter dans le même programme.
Il aura le même fonctionnement que d'habitude.

Après, ainsi que je te l'ai dit, ça ne changera en rien ni tes habitudes, ni le fonctionnement.
Mais c'est inutile, ta fonction ou la mienne renvoient la même liste, et la tienne est 3 x plus rapide

je pense avoir trouvé la solution à mon petit problème :

a) il me suffit de rentrer au départ input la valeur de [tex](n)\leqslant\sqrt{2n} [/tex] avec 2n = (30k)²

b) Est ce qu'il faut que j'utilise une deuxième variable de (n) pour crible_G; par exemple

def carre(n)
     retourn n*n


Par exemple je veux utiliser pour le crible _G [tex]carre(n)/2[/tex], afin de cribler jusqu'à 30k² / 2 les entiers [tex]\equiv{(30k)^2}[P_i] [/tex]
Ce qui me donnera les nombres premiers entre [tex][N ; 2N][/tex]

c) Puis pour la deuxième fonction qui est le crible _G , il suffit d'utiliser la valeur (n) tel que: ((carre(n) / 2) sans faire appel à la deuxième variable ci-dessus en b) par exemple :


[def crible_G ((carre(n)) / 2):   au lieu de  def crible_G(n)
  nombres = n*n*/2 *1[1]  "au lieu de nombres = n*[1] " ou, nombres = carre(n)/2 *[1]
  nombres[0] = 0
  p = eratostene(n)  au lieu de (math.sqrt(2*n))
  lenp = len(p)
  r = []
  for i in range(lenp):
 

Ou bien il faudrait rentrer deux valeurs de (n) la première pour Eratosthène  = 30k
la deuxième pour crible_G  [tex](n) = (30k)^2 / 2[/tex] mais est ce faisable...?

Dernière modification par LEG (26-01-2018 08:15:05)

Hors ligne

#32 26-01-2018 19:01:33

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 302

Re : crible en python

Bonsoir,

Je ne suis pas très sûr de comprendre ce que tu veux bricoler...
Mais, techniquement, si j'ai compris, oui, c'est faisable
Tu veux envoyer 30k à Eratostene ?
No pb.
Tu choisis n, tel que n=30k
puis pour crible_G() tu utilises crible_G(n).
Dans crible G(n)
* tu écris p=eratostene(n)
* tu écris : nombres =[1]*(n*n//2)


Mais Quelle valeur fournis-tu ici :
premiersNa2N(n)
le n = 30k ?

Il faut que tu saches que la variable n que utilises dans la fonction eratostene et la variable n que tu utilises dans la fonction crible_G sont des variables locales qui portent le même nom mais sont différentes et ne sont pas visibles à l'extérieur.

Je peux même faire :
Input ("Entrer un entier n"),n
crible_G(30*n)
avec
def  crible_G(n):
     nombres=[1]*(n**2//2)
     p=eratostene(n)

Supposons n=500 : à l'arrivée dans crible_G(n), le n vaudra  15000 mais seulement 500 à l'extérieur...

Et si tu ne veux pas n=15000 pour eratostene(n), c'est à l'appel que ça se passe...
Supposons que dans eratostene tu veuilles [tex]n=E(\sqrt(15000))[/tex],
et bien, depuis crible_G tu écris p=eratostene(int((2*n)**0.5))
Et tu laisses :
def eratostene(n):


Ce qui fait qu'à l'extérieur des fonctions n = 500
dans crible, n= 15000
dans eratostene, n=173...
Tu piges le principe ?
Et pour
premiersNa2N(n) que vaut le n ?
compte = compteInfN(liste1, n) que vaut le n ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#33 27-01-2018 10:07:41

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

Re : crible en python

Boniour
@Yoshi, tu as parfaitement compris ce que je veux modifier dans ce programme crible_G. Excuse de ne pas avoir répondu hier soir...

yoshi a écrit :

Bonsoir,

Mais, techniquement, si j'ai compris, oui, c'est faisable
Tu veux envoyer 30k à Eratostene ?
No pb.
Tu choisis n, tel que n=30k
puis pour crible_G() tu utilises crible_G(n).
Dans crible G(n)
* tu écris p=eratostene(n)
* tu écris : nombres =[1]*(n*n//2)

Ok je comprend parfaitement cette partie, mais je ne savais pas l'écrire , j'avais mis le [1] après (n*n//2) dans nombres = ,
pour p= eratosthne(n) pas de problème
mais pour eratosthene je veux lui envoyer n=30k qui est la racine carrée de 2*30k, comme ça, je ne change rien dans la première partie def eratostene (n)

et je vais me servir de ce n pour le reste; Ton idée est peut être plus simple à écrire ....

exemple [tex]2n = 900[/tex] , donc [tex]n=E(\sqrt(900))= 30[/tex] ce qui ne changera rien ci-dessus p= e....; et nombres=[1]*....
Mais la partie, la limite n que va cribler eratostene serra bien [tex]n\leqslant\sqrt{2*30k}[/tex] et non pas ce qui se passe ,ie; jusqu'à 2n....ce qui alourdit et prend du temps inutilement...

Mais Quelle valeur fournis-tu ici :
premiersNa2N(n)
le n = 30k ?

Comme tu t'en doute : cela serra donc :premiersNa2N(n*n//2)

Il faut que tu saches que la variable n que utilises dans la fonction eratostene et la variable n que tu utilises dans la fonction crible_G sont des variables locales qui portent le même nom mais sont différentes et ne sont pas visibles à l'extérieur.

Ca je l'avais compris...mais il faut que je modifie les Lignes de def crible_G , partout où il y a le n qui est utilisé ; et je pense que je dois mal écrire les modifications.... puisque cela me met des erreurs que je ne comprend pas....

Je peux même faire :
Input ("Entrer un entier n"),n
crible_G(30*n)
avec
def  crible_G(n):
     nombres=[1]*(n**2//2)
     p=eratostene(n)

Ca , serait très bien, mais il faut modifier toutes les variable qu'il y a dans def eratostene (n) jusqu'à def crible_G...y compris les lignes input.....; qui de toutes façons, dans les deux cas je vais modifier et en supprimer, celles relatives à eratosthene  et je n'en garde que 2 ou 3 utilisant le logarithme de [tex]\pi(n)[/tex] et [tex]\pi(2n)[/tex] et voir [tex]\pi(2n)[/tex] - [tex]\pi(n)[/tex]


Supposons n=500 : à l'arrivée dans crible_G(n), le n vaudra  15000 mais seulement 500 à l'extérieur...

Et donc si je suis bien, 2n = 30000... ?

Et si tu ne veux pas n=15000 pour eratostene(n), c'est à l'appel que ça se passe...
Supposons que dans eratostene tu veuilles [tex]n=E(\sqrt(15000))[/tex],
et bien, depuis crible_G tu écris p=eratostene(int((2*n)**0.5))
Et tu laisses :
def eratostene(n):

Oui je comprends mais je veux :[tex]n=E(\sqrt(2*15000))[/tex] je suppose que ce que tu as écrit de puis crible_G  : p=eratostene(int((2*n)**0.5)),  correspond à racine carrée de 30000...? c'est ça....? car en dessous tu as bien calculer la rcine carrée de 30000 = 173 pour eratostene où n= 173

Mais dans ce cas: est ce que pour nombres j'écris : nombres=n*[1] car dans crible_G(n) , n vaut 15000 si j'ai bien suivi...?

Ce qui fait qu'à l'extérieur des fonctions n = 500
dans crible, n= 15000
dans eratostene, n=173...
Tu piges le principe ?

Oui , mais est ce qu'il y a d'autre ligne à modifier...? en exemple les questions que tu me poses, ci-dessous....

Et pour
premiersNa2N(n) que vaut le n ?
compte = compteInfN(liste1, n) que vaut le n ?

pour la première question: avec ton exemple de n=500; le n = 30*n =15000

pour la deuxième question: je la supprime ou je met un # devant la ligne; car cette liste ne sert plus à rien je n'ai pas besoin de savoir ou de calculer la liste d'eratostene.
par contre la liste 2 il me la faut pour savoir combien il y a de premier de 30*n à 2*30*n

Dernière modification par LEG (27-01-2018 10:21:09)

Hors ligne

#34 27-01-2018 10:46:56

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

Re : crible en python

suite du post ci-dessus , si j'ai bien suivi ton exemple 

Input ("Entrer un entier n"),n
crible_G(30*n)

en prenant n=500  pour crible_G(n) on a n=15000 , donc 2n=30000 pour eratostène on a n=173

voila ce que donnerait les lignes print, où j'ai mis un # devant les lignes qui ne servent plus, et en gardant bien tel quel :
def premiersNa2N(n)....: puisque la valeur de n vaut 30*n =15000, dans cette fonction def.....ou faut il modifier quelque chose...?

def premiersNa2N(n):
 # liste1 = eratostene(n*2)
  compte = compteInfN(liste1, n)
  liste2 = crible_G(n)
  print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
  # print("> N / log(2N) = " + str(n / math.log(2 * n)))
  #print("> Pi(2N) = " + str(len(liste1)))
  print("> Estimation du TNP Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
  print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
  print("> Estimation Pi(2N)-Pi(N) = N/log(2N) = " + str(n / math.log(2*n)))
  #print("> Avec eratosthene: On compte " + str(len(liste1)-compte) + " nombres premiers entre 1 et " + str(n))
  #print("> Avec eratosthene: On compte " + str(compte) + " nombres premiers entre "+str(n)+" et " + str(n*2))
  print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
  # print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
  # print(liste2)

Hors ligne

#35 27-01-2018 12:07:51

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

Re : crible en python

voila ce que j'ai refait la première ligne, la troisième, et la fin comme tu l'as indiquée:

def crible_G(n):
  nombres = [1]*n
  nombres[0] = 0
  p = eratostene(int((2*n)**0.5))
  lenp = len(p)
  r = []
  for i in range(lenp):
    r.append(2*n % p[i])
    j = r[i]
    while j <= n:
      nombres[j-1] = 0
      j += p[i]
  premiers = []
  print("√2N = "+str(int(math.sqrt(2*n))))
  for i in range(n-1, 0, -1):
    if nombres[i] == 1:
      premiers.append(n-i-1)
  # on regarde si il y a un reste égal à 1
  resteUn = 0
  lenr = len(r)
  for i in range(lenr):
    if r[i] == 1:
      resteUn = 1
  # si aucun reste n'est égal à 1 2*n-1 est premier
  if resteUn == 0:
    premiers.append((2*n)-1)
  return premiers


n = int(input("Entrer un entier n"),n)
crible_G(30*n)
premiersNa2N(n)
input()
 

la fenêtre dos , s'ouvre bien, je rentre la valeur de n : 500
puis entrer et la fenêtre se ferme ....donc ?????

je viens de refaire un essais
mais avec la ligne:

 n = int(input("Donnez la valeur de N : "))

et le reste comme ci-dessus
ET CA MARCHE
résultat :sqrt de 2n = 173 , v2n = 31 ça je ne sais pas ce que cela veut dire..., et on compte 73 premiers entre n et 2n
pour l'instant je n'ai pas vérifié mais je pense que cela doi être bon
@+

je vais modifier crible_Gmod 30.

Hors ligne

#36 27-01-2018 12:47:28

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

Re : crible en python

j'ai modifié les lignes car ce n'était pas les bonnes valeurs


liste2 = crible_G(30*n)
print("> On prend N = " + str(30*n) + " , donc 2N = " + str(2 * 30*n))
print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(30*n) + " et " + str(2 * 30*n))
 

il faut aussi savoir que la valeur n rentrée dans ce cas n=500  soit 30*500..
on ne crible que jusqu'à 15000 -30 c'est à dire n -1 en criblant n=501 on a bien 1494 premiers de 15000 à 30000 sachant que 2n-1, n'est pas criblé .
dans mon algo nBpremier , il m'en donne 1495...

Donc Yoshi ou je te paye un bon resto ou tu veux une bonne bouteille, pour ton dévouement avec un grand merci ......

il me reste crible_G mod 30 à modifier pour vérifier les temps mis...

Hors ligne

#37 27-01-2018 14:46:10

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

Re : crible en python

pour le crible mod 30

il me crible deux fois  crible mod 30


n = int(input("Donnez la valeur de N : "))
crible_G2(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(30*n))
print("On a "+str(nb)+" nombres premiers")
input()
 

et si je renseigne la deuxième ligne "crible_G(30*n)"


n = int(input("Donnez la valeur de N : "))
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(30*n))
print("On a "+str(nb)+" nombres premiers")
input()
 

il effectue deux fois le crible_G......?

il y a une erreur dans cette ligne...

voila je viens de modifier comme ceci :


n = int(input("Donnez la valeur de N : "))
n = 30*n
nb = len(crible_G(n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_mod(n))
print("On a "+str(nb)+" nombres premiers")
input()
 

et impeccable    ....je vais  boire un coup à ta santé....un grand merci.....
@+

Dernière modification par LEG (27-01-2018 15:07:00)

Hors ligne

#38 27-01-2018 15:10:25

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 302

Re : crible en python

Re,

Oui.

n = int(input("Donnez la valeur de N : "))
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(30*n))
print("On a "+str(nb)+" nombres premiers")

input()
Au fait, c'est quoi crible_G2 ? le même code que crible_G ?
Si oui, en bleu, c'est en double.

Modif cosmétique suggérée
Au début du programme, tu peux ajouter :
import os
et remplacer le input() final par
os.system("pause")
Ça ne change rien, sinon que c'est plus "propre"...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#39 27-01-2018 17:05:31

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

Re : crible en python

yoshi a écrit :

Re,

Oui.

n = int(input("Donnez la valeur de N : "))
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")


ok,  mais si je fais cela alors il effectue deux fois le criblage du crible _G .. mais comme je ne l'ai pas écrit exactement pareil, et que cela marche comme je l'ai écrit dans le dernier post dernier paragraphe ...j'attends qu'il finisse 30*n=1 020 000 000 si cela passe car avec l'ancienne version il tourne il tourne le furet......


Modif cosmétique suggérée
Au début du programme, tu peux ajouter :
import os
et remplacer le input() final par
os.system("pause")
Ça ne change rien, sinon que c'est plus "propre"...
@+

ça ensuite je l'essaye.

pour en revenir à ta question, pour le crible_G2 appelé maintenant crible_mod
c'est le même mais comme je l'ai expliqué un peu vite...lui il crible les entiers n congrus à1 ou P (mod Pi) avec P premier appartenant à [7 ; 29], sachant que 1 n'est pas premier donc dans le crible il est remplacé par 31...etc

voila pourquoi dans ce crible on fait un tableau de 8 Familles " suite en progression arithmétique de raison 30 et de premier terme :
{1.7.11.13.17.19.23 et 29}
ce qui permet de cribler par famille : modulo (P_i *30) une fois que les restes R ou P_i lorsque R = 0, sont positionnés au départ dans chaque Famille...

cela gagne du temps et de la place en mémoire...bien sur en supprimant dans crible_mod , la fonction : def crible_G(n)
mais cela je ne l'ai pas fait pour l'instant , car je risque de me planter dans la suppression des lignes relatif à crible_G(n)...sans altérer le fonctionnement crible_mod peut être simplement en mettant # devant def crible_G(n) et en supprimant les trois dernières lignes
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")

et je garde uniquement ce que tu as écrit en bleu...

je te joins la copie crible_mod ci dessous ce qui va te permettre de mieux comprendre...si besoin est ...


import os
import math
import time

def eratostene(n):
   n = int(n)
   m = (n-1) // 2
   b = [True]*m
   i = 0
   p = 3
   premiers = [2]
   while p*p < n:
      if b[i]:
         premiers.append(p)
         j = 2*i*i + 6*i + 3
         while j < m:
            b[j] = False
            j = j + 2*i + 3
      i += 1
      p += 2
   while i < m:
      if b[i]:
         premiers.append(p)
      i += 1
      p += 2
   return premiers


def compteInfN(liste, n):
   compte = 0
   lenListe = len(liste)
   for i in range(0, lenListe):
      if (liste[i] >= n):
         compte += 1
   return compte


def premiersNa2N(n):
   #liste1 = eratostene(n)
   liste2 = crible_G(30*n)
   print("> On prend N = " + str(30*n) + " , donc 2N = " + str(2 * 30*n))
   #print("> N / log(2N) = " + str(n / math.log(2 * n)))
   #print("> Pi(2N) = " + str(len(liste1)+len(liste2)))
   print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
   print("> Estimation Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
   print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(30*n) + " et " + str(2 * 30*n))
   #print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
   # print(liste2)


def crible_G(n):
   # INITIALISATION
   start_time = time.time()
   nombres = n*[1]
   nombres[0] = 0
   p = eratostene(int((2*n)**0.5))
   lenp = len(p)
   r = []
   print("Crible G: Initialisation: %s seconds ---" % (time.time() - start_time))

   # CRIBLAGE DES NOMBRES
   start_time = time.time()
   for i in range(lenp):
      r.append(2*n % p[i])
      j = r[i]
      while j <= n:
         nombres[j-1] = 0
         j += p[i]
   print("Crible G: Criblage des entiers 1 à n: %s seconds ---" % (time.time() - start_time))

   # EXTRACTION DES_NOMBRES_PREMIERS
   start_time = time.time()
   premiers = []
   for i in range(n-1, 0, -1):
      if nombres[i] == 1:
         premiers.append(2*n-i-1)
   # on regarde si il y a un reste égal à 1
   resteUn = 0
   lenr = len(r)
   for i in range(lenr):
      if r[i] == 1:
         resteUn = 1
   # si aucun reste n'est égal à 1 2*n-1 est premier
   if resteUn == 0:
      premiers.append(2*n-1)
   print("Crible G: Extraction premiers n à 2*n: %s seconds ---" % (time.time() - start_time))
   return premiers


def fam_reste(reste, p8):
   i = 0
   while i < 8 and reste % 30 != p8[i]:
      i += 1
   if i == 8:
      return -1
   else:
      return i


# On travaille avec 8 familles (1, 7, 11, 13, 17, 19, 23, 29)
# ATTENTION: n doit être multiple de 15
def crible_mod(n):
   # INITIALISATION
   start_time = time.time()
   nbcell = int(n/30)
   nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
   p = eratostene(int((2*n)**0.5))
   p = p[3:]
   lenp = len(p)
   r = []
   p8 = [1, 7, 11, 13, 17, 19, 23, 29]
   pfam = []
   print("Crible mod : Initialisation: %s seconds ---" % (time.time() - start_time))

   # FAMILLES POUR CHAQUE Pi
   start_time = time.time()
   for i in range(lenp):
      r.append(2*n % p[i])
      pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
      j = r[i]
      incr = p[i]*2
      d_c = str(j)[-1]
      # On elimine les restes pairs
      if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
         j += p[i]
         d_c = str(j)[-1]
      while j < n:
         if d_c == '5' or j % 3 == 0:  # on passe au suivant
            fam = -1
         elif d_c == '1':  # on vérifie 1 et 11
            if j % 30 == p8[0]:
               fam = 0
            else:
               fam = 2
         elif d_c == '3':  # on vérifie 13 et 23
            if j % 30 == p8[3]:
               fam = 3
            else:
               fam = 6
         elif d_c == '7':  # on vérifie 7 et 17
            if j % 30 == p8[1]:
               fam = 1
            else:
               fam = 4
         else:  # on vérifie 19 et 29 (d_c = 9)
            if j % 30 == p8[5]:
               fam = 5
            else:
               fam = 7
         if fam != -1 and pfam[i][fam] == 0:
            pfam[i][fam] = j
         j += incr
         d_c = str(j)[-1]

   print("Crible mod : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))

   # ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE Pi
   start_time = time.time()
   lenpfam = len(pfam)
   for i in range(lenpfam):
      for j in range(8):
         index = int((pfam[i][j] - p8[j]) / 30)
         while index < nbcell:
            nombres[j][index] = 0
            index += p[i]
   print("Crible mod : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

   # AFFICHAGE
   for i in range(8):
      count = 0
      for cell in nombres[i]:
         if cell == 1:
            count += 1

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


n = int(input("Donnez la valeur de N : "))
n = 30*n
nb = len(crible_G(n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_mod(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
 

Dernière modification par LEG (27-01-2018 17:26:02)

Hors ligne

#40 27-01-2018 17:24:14

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

Re : crible en python

yoshi a écrit :

Re,

n = int(input("Donnez la valeur de N : "))
crible_G(30*n)
nb = len(crible_G(30*n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_G2(30*n))
print("On a "+str(nb)+" nombres premiers")

input()
@+

attention ça cela ne marche pas il se produit un double criblage de cribl_G
il me faut bien écrire comme je l'ai fait dans le programme joins :


n = int(input("Donnez la valeur de N : "))
n = 30*n
nb = len(crible_G(n))
print("On a "+str(nb)+" nombres premiers")
print("---------------------------------------------------------")
nb = len(crible_mod(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")
 

Hors ligne

#41 27-01-2018 18:27:35

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 302

Re : crible en python

Re,

C'est toi le mieux placé pour voir ce qui va, ce qui ne va pas.
Je regarderai ça de plus près plus tard...
Je t'avais écrit :

Au fait, c'est quoi crible_G2 ? le même code que crible_G ?
Si oui, en bleu, c'est en double.

Et là, c'est maintenant crible_mod (qui "semble" bien plus touffu que le crible_G de départ...

Bon, maintenant, on dirait bien que tu es mûr pour continuer à programmer en Python... ^_^
Python est très "user friendly"...
Débuter va relativement vite et Python comporte un nombre imposant de modules importables...
Il y en a 2 ou 3 dédiés au calcul scientifique en général et mathématique en particulier.
A ma connaissance, il est le seul langage à permettre
- en natif de travailler avec des entiers de très très grandes longueurs : la seule limite étant la taille de la RAM de la machine
- via importation d'un module de travailler avec 100, 200, 1000... chiffres décimaux...

Au fait, c'est cela que tu as implémenté : www.bibmath.net/forums/viewtopic.php?id=9001&p=3 (dernier post) ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#42 27-01-2018 21:23:16

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

Re : crible en python

yoshi a écrit :

Re,

C'est toi le mieux placé pour voir ce qui va, ce qui ne va pas.
Je regarderai ça de plus près plus tard...
Je t'avais écrit :

Et là, c'est maintenant crible_mod (qui "semble" bien plus touffu que le crible_G de départ...

il est pareil qu crible_G, si ce n'est que l'on a supprimé les 2n , 3n et 5n, il est un peu plus chia....à programmer..

le crible_G lui crible de 1 à n = n*30 , les entiers sont représentés aussi par des 1, donc pour n= 500 il y en a 15000 au lieu de 4000,
dans cribl_mod, car : 15000 /3,75 = 4000; ou si tu préfères pour n = 500; 500 * 8 = 4000 entiers congrus à 1 ou p [30] on a éliminé 73,333...% des entiers naturels > 0....etc

et dans crible_G, on par du reste R quelque soit sa forme pair ou impair et on rajoute P_i , biens sûr si R = 0 et bien tu pars de P_i mais le principe et le même que crible Eratosthène...C'est pour cela que ce crible, prouve que le nombre de premiers [n ; 2n] est obligatoirement
< à pi(n) ... même si il n'y avait pas de nombres premiers entre [tex]\sqrt{n}[/tex] et [tex]\sqrt{2n}[/tex]....c'est facile à prouver....
il en ressortira que G(n) fonction qui compte les entiers [tex]\not\equiv{2n}[P_i][/tex] l, c'est à dire les nombres premiers q appartenant à [n ; 2n]....

Au fait, c'est cela que tu as implémenté : www.bibmath.net/forums/viewtopic.php?id=9001&p=3 (dernier post) ?
@+

Non pas du tout, de toutes façons, les entiers dans le tableau des 8 familles relatif au crible_mod ils sont représenté par 8 colonne de 1
1.1.1.1.1.1.1.1
1.1.1.1.1.1.1.1
1.1.1.1.1.1.1.1
1.1.1.1.1.1.1.1
1.1.1.1.1.1.1.1
...etc ...
jusqu'à lim n ,  si n= 500 cela donne 500 lignes de 8 colonne et tu auras criblé de 1 à 15000 par colonne , mais le premier 1 est criblé, si et seulement si, dans les restes R de n*30 par P_i si il existe un R = 1 alors le premier 1 se transforme en 0 et donc 2n-1 = n'est pas un nombre premier, et inversement si il n'y a pas de R = 1  ("exit les 2m,3m et 5m" bien entendu).

Par exemple dans la première colonne d'entiers [tex]\equiv{1}[30][/tex] le premier 1  est marqué 0, le deuxième 1 = 31 est aussi marqué 0 donc 30000 -1 n'est pas premier, ni 30000 - 31.

la première ligne de 1, représente:
1.7.11.13.17.19.23.29     
et ensuite tu rajoutes 30 dans chaque colonne jusqu'à n

("donc la première ligne est < 30 ; c'est pour cela qu'il y a un décalage lorsque l'on crible, je rajoute toujours 1 à n") afin de cribler,
30000 -1  car dans le programme en principe si R = 1, alors 2n -1 n'est pas premier or lorsque l'on indique n = 500, en réalité on a 499*30 -1 = 14969 , puisque la première ligne ne peut valoir ou être > 30, alors que si je prend n+1 donc = 501, et (501 - 1)*30 - 1= 14999.

et on part du reste R si et seulement si il est congru à 1 ou P modulo 30 afin de le placer dans sa famille et si R = 0 donc la on part de P_i relatif à sa famille et on calcul les 7  autres entiers, tel que R + P_i congru à 1 ou P modulo 30....
c'est ce qui est écrit dans le programme....

je suis mûr pour les cribles mais surement pas pour Python....Lollll. je n'aime pas la langue anglaise de plus je programmerai rien d'autre avant des lustres....en principe....C'est le seul crible qu'il me fallait faire programmer....

Mais Merci de m'avoir poussé à chercher , à regarder : programmer en Python, pour essayer de comprendre ce que mon petit fils à fait ...etc, et surtout ton dévouement..
Bonne soirée Yoshi et pour une bonne bouteille ou repas cela tient toujours.....
A+

Dernière modification par LEG (27-01-2018 21:55:27)

Hors ligne

#43 28-01-2018 16:08:14

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

Re : crible en python

Bonjour
@Yoshi voila ce que cela donne en temps par tranche de 30 000 000, ou en augmentant n de 1 000 000
comme tu le verras, j'ai bloqué la fonction crible_G(n) en mettant # devant les lignes de fonction dont je n'ai pas l'utilité....
Ce qui permet de cribler un peu plus loin et de diviser le temps par 2...

Mais je ne sais pas si c'est Python ou la mémoire dos, car je ne peux pas cribler n = 38 000 000 ; 1 140 000 000 .
Avec l'algo Nb premier je crible n= 15 000 000 000 de cellules = 1; soit jusqu'à 450 000 000 000; "mais par famille" et en C++.
Or, si on regarde, cela ne fait pour crible_mod30 que 38 000 000 * 8 = 304 000 000 de cellules = 1 .
Cela me suffit....

Le but étant toujours de cribler de 7 à 30*n, pour obtenir le nombre de nombres premiers de n à 2n et vérifier la fonction [tex]\frac{N}{Ln 2N}[/tex] relatif à G(n) .... tel que : 30(n+1) / Ln 60(n+1) vaut environ 2*(30n / Ln 60(n) - 30(n-1) / Ln 60(n-1)


A+

Dernière modification par LEG (01-05-2018 11:13:03)

Hors ligne

#44 29-01-2018 17:48:44

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

Re : crible en python

Bonjour :
@Yoshi est ce que ce fichier , pour le programme cible_mod30 est plus facile à comprendre , c'est ce que mon petit fils aurait dû programmer par Famille, et non les 8 Familles d'un coup. Ce qui je pense aurait été plus simple, et plus facile...Tout comme il fallait faire appel à Eratosthène , mais jusqu'à racine carrée de 2n...ça encore avec la modification que tu m'as indiquée cela résout ce problème ..
donc voici le lien de ce petit fichier word...


bonne lecture.A+

Dernière modification par LEG (01-05-2018 11:13:25)

Hors ligne

#45 29-01-2018 19:45:42

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 302

Re : crible en python

Re,

Patience, Je suis occupé à répondre aux demandes d'aire et quand suite à une fausse manipe (ça m'arrive !), paf !, je perds tout, je suis obligé de recommencer... Et comme je ne tape pas vite...
D'autre part, là j'ai ma revue de mars qui m'attend : j'ai besoin de trouver 20 pages...
10 pages de vie de l'Association + 10 pages de sujets d'intérêt général...
Oh, je les trouverais !
Mais quand j'ai les 10 premières pages, elles sont généralement manuscrites : la reconnaissance de caractères (en anglais OCR ^_^) via le scanner est inopérante.
Dons là jusqu'au 15 mars, j'aurai des choix à faire, hélas !

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#46 30-01-2018 06:50:20

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

Re : crible en python

re, Je comprend parfaitement Yoshi, d'autant que je vais envoyer à mon petit fils, la modif que tu m'as apporté, et avec ce fichier qu'il me modifie les lignes relatives à crible_mod30; si .... il n'est pas trop pris par sa préparation et sa remonté des notes, afin qu'il puisse être admis à son concourt sur Montréal ....je t'ai envoyé le fichier pour info....et je te remercie encore, bon courage en attendant....
A+ LEG

Hors ligne

#47 02-02-2018 11:57:42

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

Re : crible en python

Bonjour
@Yoshi :
Pour info voici le lien du fichier qui donne les explication de cet algorithme crible_mod30; que mon petit fils va modifier ce  Week-end , pour cribler par famille.
j'ai déjà modifier afin de simplifier le criblage-mod30 , dont le programme python actuel est en fin de document (il n'y a eut en définitive, que deux lignes à modifier suivant tes instructions...la ligne de def eratostene (2*n**.05)) et la dernière,
n = int(input("donner la valeur N +30 : "))

de ce fait il prend la valeur n = 30k jusqu'à 4 500 000 000, au lieu de 975 000 000 ....ce qui permet de voire l'évolution de la répartition des nombres premiers [n ; 2n]; par tranche de 30 000 000. et de vérifier le rapport (n / 3,75) / Pn qui est le nombre de premiers de n à 2n.etc ...etc
Bonne journée.

Dernière modification par LEG (01-05-2018 11:13:48)

Hors ligne

#48 15-03-2018 10:29:20

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

Re : crible en python

Bonjour
j'en suis toujours au même point. je n'ai pas réussi à modifier le programme ci-dessous pour qu'il ne travaille "crible" que dans une seule famille...
j'ai remplacé 8 par 1 dans cette ligne:   nombres = [[1 for _ in range(nbcell)] for _ in range(8)] pour n'avoir qu'une colonne de [1] ou ligne de [1]

j'ai remplacé cette ligne : p8 = [1, 7, 11, 13, 17, 19, 23, 29]  par, p8 = 1 pour ne travailler que dans la famille 1 modulo 30

la ligne en dessous pfam = [] , je n'y ai pas touché mais je ne sais pas quel est son rôle...?

j'ai mis un # devant les lignes :   #elif d_c == '3':  # on vérifie 13 et 23 ; #elif d_c == '7':  # on vérifie 7 e17 ,et, #else:  # on vérifie 19 et 29 (d_c = 9) afin qu'elle ne soient pas pris en compte dans le programme

je suppose que cette ligne:  pfam.append([0, 0, 0, 0, 0, 0, 0, 0])   pose problème si je travaille que dans une colonne [1]...?

et ensuite j'ai remplacé le (8) par (1) dans les lignes for j in range(8)
sans résultat....?

voici la partie du programme à modifier à partir de la ligne 102 dans pycharme:


# ATTENTION: n doit être multiple de 30
def crible_mod30(n):
  # INITIALISATION
  start_time = time.time()
  nbcell = int(n/30)
  nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
  p = eratostene(int(n))
  p = p[3:]
  lenp = len(p)
  r = []
  p8 = [1, 7, 11, 13, 17, 19, 23, 29]
  pfam = []
  print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

  # FAMILLES POUR CHAQUE Pi
  start_time = time.time()
  for i in range(lenp):
    r.append(2*n % p[i])
    pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
    j = r[i]
    incr = p[i]*2
    d_c = str(j)[-1]
    # On elimine les restes pairs
    if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
      j += p[i]
      d_c = str(j)[-1]
    while j < n:
      if d_c == '5' or j % 3 == 0:  # on passe au suivant
        fam = -1
      elif d_c == '1':  # on vérifie 1 et 11
        if j % 30 == p8[0]:
          fam = 0
        else:
          fam = 2
      elif d_c == '3':  # on vérifie 13 et 23
        if j % 30 == p8[3]:
          fam = 3
        else:
          fam = 6
      elif d_c == '7':  # on vérifie 7 et 17
        if j % 30 == p8[1]:
          fam = 1
        else:
          fam = 4
      else:  # on vérifie 19 et 29 (d_c = 9)
        if j % 30 == p8[5]:
          fam = 5
        else:
          fam = 7
      if fam != -1 and pfam[i][fam] == 0:
        pfam[i][fam] = j
      j += incr
      d_c = str(j)[-1]

  print("Crible mod30 : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))

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

  # AFFICHAGE
  for i in range(8):
    count = 0
    for cell in nombres[i]:
      if cell == 1:
        count += 1

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


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

je remet si-dessous l'intégralité du programme qui fonctionne bien dans les 8 Familles modulo 30 : Si quelqu'un peut me dire ce que je dois modifier, pour que le crible fonctionne que dans une Famille par exemple la famille p8 = 1 , Ca serait sympa....Dans l'attente Merci...

import os
import math
import time


def eratostene(n):
  n = int((2*n)**0.5)
  m = (n-1) // 2
  b = [True]*m
  i = 0
  p = 3
  premiers = [2]
  while p*p < n:
    if b[i]:
      premiers.append(p)
      j = 2*i*i + 6*i + 3
      while j < m:
        b[j] = False
        j = j + 2*i + 3
    i += 1
    p += 2
  while i < m:
    if b[i]:
      premiers.append(p)
    i += 1
    p += 2
  return premiers


#def compteInfN(liste, n):
  compte = 0
  lenListe = len(liste)
  for i in range(0, lenListe):
    if (liste[i] >= n):
      compte += 1
  return compte


#def premiersNa2N(n):
  #liste1 = eratostene(n)
  liste2 = crible_G(n)
  print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
  #print("> N / log(2N) = " + str(n / math.log(2 * n)))
  #print("> Pi(2N) = " + str(len(liste1)+len(liste2)))
  print("> Estimation Pi(2N) = N/log(N)+ N/log(2N) = " + str(n / math.log(n)+n / math.log(2 * n)))
  print("> Estimation Pi(2N) = 2N/log(2N) = " + str(2*n / math.log(2*n)))
  print("> Avec goldbach: On compte " + str(len(liste2)) + " nombres premiers entre " + str(n) + " et " + str(2 * n))
  #print("> Voici la liste des nombres premiers entre " + str(n) + " et " + str(2 * n) + " :")
  # print(liste2)


#def crible_G(n):
  # INITIALISATION
  start_time = time.time()
  nombres = n*[1]
  nombres[0] = 0
  p = eratostene(int(n))
  lenp = len(p)
  r = []
  print("Crible G: Initialisation: %s seconds ---" % (time.time() - start_time))

  # CRIBLAGE DES NOMBRES
  start_time = time.time()
  for i in range(lenp):
    r.append(2*n % p[i])
    j = r[i]
    while j <= n:
      nombres[j-1] = 0
      j += p[i]
  print("Crible G: Criblage des entiers 1 à n: %s seconds ---" % (time.time() - start_time))

  # EXTRACTION DES_NOMBRES_PREMIERS
  start_time = time.time()
  premiers = []
  for i in range(n-1, 0, -1):
    if nombres[i] == 1:
      premiers.append(nombres[i] == 1)
  # on regarde si il y a un reste égal à 1
  resteUn = 0
  lenr = len(r)
  for i in range(lenr):
    if r[i] == 1:
      resteUn = 1
  # si aucun reste n'est égal à 1 2*n-1 est premier
  if resteUn == 0:
    premiers.append(2*n-1)
  print("Crible G: Extraction premiers n à 2*n: %s seconds ---" % (time.time() - start_time))
  return premiers


#def fam_reste(reste, p8):
  i = 0
  while i < 8 and reste % 30 != p8[i]:
    i += 1
  if i == 8:
    return -1
  else:
    return i


# On travaille avec 8 familles (1, 7, 11, 13, 17, 19, 23, 29)
# ATTENTION: n doit être multiple de 30
def crible_mod30(n):
  # INITIALISATION
  start_time = time.time()
  nbcell = int(n/30)
  nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
  p = eratostene(int(n))
  p = p[3:]
  lenp = len(p)
  r = []
  p8 = [1, 7, 11, 13, 17, 19, 23, 29]
  pfam = []
  print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

  # FAMILLES POUR CHAQUE Pi
  start_time = time.time()
  for i in range(lenp):
    r.append(2*n % p[i])
    pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
    j = r[i]
    incr = p[i]*2
    d_c = str(j)[-1]
    # On elimine les restes pairs
    if d_c == '0' or d_c == '2' or d_c == '4' or d_c == '6' or d_c == '8':
      j += p[i]
      d_c = str(j)[-1]
    while j < n:
      if d_c == '5' or j % 3 == 0:  # on passe au suivant
        fam = -1
      elif d_c == '1':  # on vérifie 1 et 11
        if j % 30 == p8[0]:
          fam = 0
        else:
          fam = 2
      elif d_c == '3':  # on vérifie 13 et 23
        if j % 30 == p8[3]:
          fam = 3
        else:
          fam = 6
      elif d_c == '7':  # on vérifie 7 et 17
        if j % 30 == p8[1]:
          fam = 1
        else:
          fam = 4
      else:  # on vérifie 19 et 29 (d_c = 9)
        if j % 30 == p8[5]:
          fam = 5
        else:
          fam = 7
      if fam != -1 and pfam[i][fam] == 0:
        pfam[i][fam] = j
      j += incr
      d_c = str(j)[-1]

  print("Crible mod30 : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))

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

  # AFFICHAGE
  for i in range(8):
    count = 0
    for cell in nombres[i]:
      if cell == 1:
        count += 1

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


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

Dernière modification par LEG (15-03-2018 10:32:50)

Hors ligne

#49 16-03-2018 14:59:18

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 12 302

Re : crible en python

Bonjour,

J'ai maintenant du temps, je vais essayer de comprendre
1. Ton histoire de familles
2. Ce que fait ton programme.

Je vais remplacer la variable Pï  qui me perturbe (à cause du Latex) par une autre...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#50 16-03-2018 15:43:26

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

Re : crible en python

Bonjour
@Yoshi : c'est quoi la variable Pï...? tu veux parler des nombres premiers [tex] P_i[/tex]...? et des restes [tex] R_i[/tex] de la division Euclidienne de [tex]\frac{30k}{P_i} = R_i[/tex]....

Les familles, son 8 suites en progression arithmétique de raison 30 et de premiers termes 1 ou P premier appartenant à [tex][7 ; 29][/tex]



A+ ..Merci...

Dernière modification par LEG (01-05-2018 11:14:43)

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 ?11 + 49
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