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 20-01-2018 17:11:03

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

crible en python

Bonjour à tous
j'aurai besoin d'aide svp pour modifier ce programme fait par mon petit fils qui est reparti sur Chicoutimi Québec...
la deuxième partie ligne 53,  ( def crible_G(n): ) c'est le crible des congruences, restituant les nombres premiers entre n et 2n, mais pour ce faire, on crible les entiers de $1\: à\: n\equiv {2n}[P_i]$ cette partie je n'y touche pas...
Mais :
que dois je modifier dans la deuxième partie def cribleG(n) pour extraire les nombre premiers j%30 == 1, en ne travaillant que dans la famille 1 modulo 30.
donc cela revient à cribler de 1 à n//30  soit la suite arithmétique de raison 30 ...SVP...merci d'avance

***************************************************************************
dernière version du cribleG(n) , 04/10/2018.


import os
import math
from time import time


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
  return prime_list

def demander_N():
  n = input("Donnez N: ")
  n = int(n.strip().replace(" ", ""))
  n = int(30 * round(float(n)/30))
  print(f"On prend N = {n}  (30 * {int(n/30)})")
  return n

def premiersNa2N(n):
  liste = crible_G(eratostene(n), n)
  #print("> On prend N = " + str(n) + " , donc 2N = " + str(2 * n))
  #print(">(Estimation Pi(2N)-Pi(N) avec la fonction 2 du TNP)= N / log(2N) = " + str(n / math.log(2 * n)))
  #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)))

def crible_G(premiers, n):
  start_crible = time()
 
  # On génère une "suite arithmétique 1 de raison 30", de (N/30)*1 cellules
  crible = n*[1]
  crible[0] = 0
  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
    # On crible directement à partir de l'index du reste avec pi par pas de pi
    for index in range(reste, lencrible, premier):
      crible[index] = 0

  total = sum(crible)
  #lprint("crible:", crible)
  print(f"Nombre premiers criblés entre {n} et {n2}: {total} ----- {int((time()-start_crible)*100)/100}")

n = demander_N()
premiersNa2N(n)
os.system("pause")

 


Puis faire la somme des [1] pour connaître le nombre d'entiers de $1\: à\: n\equiv {2n}[P_i]$ permettant de compter les nombres premiers , de $[n ; 2n]$.

Dernière modification par LEG (23-10-2020 10:10:33)

Hors ligne

#2 20-01-2018 18:47:37

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

Re : crible en python

Salut,

Tu veux absolument garder cette version de la fonction eratosthene ?
L'as-tu testée ?
Jusqu'à n=81, ok, pas de pb...
A partir de 82, on attend, attend, attend...
Je te propose ça à la place :

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)

qui m'affiche
[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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
en moins d'une seconde...
Si dans l'appel  premiers=eratosthene (n), je remplace n par nn ([tex]E(\sqrt{2n})[/tex]), je n'ai plus que
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43] (nn= 44).

J'ai essayé de remplacer dans le erato fourni, m=(n-1)//2, par m=int((2*n)**0.5)
Instantané jusqu'à n = 81 et à partir de n= 82, ça tourne, tourne, tourne...
Pour le moment c'est un mystère : je ne comprends pas...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 20-01-2018 19:20:23

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

Re : crible en python

Bonsoir yoshi

le programme que j'ai mis sur le site , il est écrit avec pycharm, j'ai deux "applications" 1) crible_g et 2) crible_modulo 30 , je clic sur l'un ou l'autre, cela m'ouvre une fenêtre dos , je rentre la valeur de n par ex 900 000 et j'ai le résultat de suite par exemple pour n = 300 000
j'ai 23101 nombres premiers avec Eratosthène et avec crible g, entre 300 000 et 600 000

mon souci je voudrai simplement que dans le début de ce programme on évite à Eratosthène de cribler jusqu'à n, ce qui ne sert à rien  mais simplement jusqu'à la racine de 2n; car on a besoin uniquement de nombres premiers $p_i\in{P(n)}$ ensembles des nombres premiers $P\leqslant\sqrt{2n}$

mais je ne m'occupe pas d'extraire les premiers de 1 à n avec Eratosthène je suppose qu'il le fait automatiquement, puisque dans le résultat  il m'indique qu' avec Eratosthène il trouve 23101 premiers entre n et 2n  donc il crible jusqu'à n les entiers non nuls de 1 à n, non congrus à 2n[pi] ; puis il vérifie si le crible_g à le bon résultat... Je sais que le crible G fonctionne parfaitement donc je voudrais supprimer cette partie d'ératosthène > à sqrt de 2n, qui ne sert à rien

c'est pour cela que j'ai copié l'intégralité du programme pycharme..

je suppose que tu as essayé l'intégralité du programme , et je pense qu'il doit falloir remplacer juste les deux ou trois premières lignes pour appliquer Eraotosthène <= sqrt de 2n...nonb?

est que tu veux que je te joigne par mail les deux applications Crible G et crible modulo 30 afin que tu puisses voir comment cela fonctionne...

Dernière modification par LEG (23-10-2020 10:18:31)

Hors ligne

#4 20-01-2018 19:31:39

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

Re : crible en python

@Yoshi, comment je joins un fichier PDF ...?

Hors ligne

#5 20-01-2018 19:45:43

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

Re : crible en python

LEG a écrit :

@Yoshi, comment je joins un fichier PDF ...?

voila un premier lien :
https://www.cjoint.com/c/HAusKU5JQaW
crible-g voici le lien
https://www.cjoint.com/c/HAusMn4Q4AW
crible mod 30 voici le lien
https://www.cjoint.com/c/HAusNFZ2bzW

je suppose qu'avec pycharm-edu- 2017.3 ; en copiant et collant les deux programmes, tu auras ensuite les deux applications , qui fonctionnent avec python:
3.6.3 -fr_64262-64 et ou 3.6.4-amd 64

Hors ligne

#6 20-01-2018 19:55:55

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

Re : crible en python

voici ce que cela donne avec pycharm :

https://www.cjoint.com/c/HAus2CetGwW

crible mod 30
https://www.cjoint.com/c/HAus3jDkFHW

Hors ligne

#7 20-01-2018 20:41:37

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

Re : crible en python

yoshi a écrit :

Si dans l'appel  premiers=eratosthene (n), je remplace n par nn ([tex]E(\sqrt{2n})[/tex]), je n'ai plus que
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43] (nn= 44).

J'ai essayé de remplacer dans le erato fourni, m=(n-1)//2, par m=int((2*n)**0.5)
Instantané jusqu'à n = 81 et à partir de n= 82, ça tourne, tourne, tourne...
Pour le moment c'est un mystère : je ne comprends pas...

@+

je suppose qu'effectivement il faut uniquement faire l'appel premiers= eratosthene nn ([tex]E(\sqrt{2n})[/tex]) car on a besoin uniquement des nombres premiers Pi ([tex]E(\sqrt{2n})[/tex]) pour le crible_G ou crible mod 30

et on supprime les autres lignes d'eratosthène , en gardant tout le reste relatif au crible _G, en supprimant aussi les lignes prints

 
 liste1 = eratostene(n*2)
  compte = compteInfN(liste1, 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))

Hors ligne

#8 21-01-2018 11:31:51

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

Re : crible en python

Re,

Non je n'ai pas fait tout ça...
Je me suis occupé de la def eratostène(n) que j'ai transformé en script seul.
Là, je peux dire qu'il fonctionne jusqu'à n=81 et à partir de n=82, je n'ai pas le courage d'attendre... Pourquoi ?
Je ne comprends pas ce que vient faire Pi ([tex]\pi[/tex] ?) là-dedans.
Je t'ai fait une proposition.
Maintenant, tu sembles savoir ce que tu fais mieux que moi... il est donc inutile que je me casse plus la tête.
Si tu fais référence à des nos de ligne, mets ton code entre balises code et modifie en code=Python.

Ensuite, c'est Pycharm qui met des indentations de 2 caractères ? Les recommandations officielles disent 4 et je suis d'accord : 2 c'est plus difficile à lire...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#9 21-01-2018 14:44:47

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

Re : crible en python

yoshi a écrit :

Re,

Non je n'ai pas fait tout ça...

Je ne comprends pas ce que vient faire Pi ([tex]\pi[/tex] ?) là-dedans.
.
Maintenant, tu sembles savoir ce que tu fais mieux que moi...

@+

Bonjour Yoshi
si je savais programmer je n'aurai pas demandé de l'aide ..je n'y comprend strictement rien en programme...
je ne comprend pas non plus ton interrogation au sujet de ce que vient faire Pi ([tex]\pi[/tex] ?)
Je pense que je me suis mal exprimé : Pi est un nombre premier appartenant à l'ensemble des nombres P(n)< à racine de 2n .

ce que je sais , c'est que le programme à été fait pour cribler les entiers de 1 à n congrus à 2n (mod Pi) avec Pi premier et < ou = sqrt de 2n.

Mon petit fils a impliquer Eratosthène de 1 à n et même de 1 à 2n afin de comparer le crible_G qui crible comme Eratosthène, mais : les congruents de Pi et non leurs multiples , c'est le même principe...! Si ce n'est que l'on part du reste R de 2n par Pi et puis on marque tous les congruents modulo Pi par pas de  Pi jusqu'a la lim n fixée au départ..


voila pourquoi on a besoin d'Eratosthène, mais uniquement les nombres premiers Pi < sqrt de 2n....

Je ne sais donc pas qu'elles lignes je dois occulter dans def eratosthene sans altérer le fonctionnement de mon programme....?

Pour cribler avec crible _g

on a besoins; des Pi <= sqrt de 2n
puis : des reste R de la division de 2n par Pi
ensuite , on part du reste R avec leur Pi et on barre par pas de Pi,  les entiers congrus à 2n (mod Pi) jusqu'à limite n fixée au départ, et on réitère avec le prochain Pi et son reste R..

à la fin on compte les entiers qui n'ont pas été barrés, comme dans Eratosthène...ce qui nous donne le nombre de premiers de n à 2n...

au lieu de marquer les entiers de 1 à n on les représente avec des 1 jusqu'a lim n

lorsqu'un entier est barré on remplace le 1 par 0 . à la fin on compte les 1 qui ne sont donc pas congrus à 2n mod Pi....!

Exemple_: n = 120 donc 2n = 240 , sqrt 240 = 15 ; donc les Pi sont {2,3,5,7,11 et 13}
les restes R sont  {0, 0, 0 ,2 , 9 et 6}

il n'y a pas de reste R =1, donc le premier entier 1, n'est pas marqué 0, et 2n - 1  est premier q.

pour les R = 0 on part directement de leur Pi : 2 et on marque tous les 2 nombres...puis 3 et on marque tous les 3 nombre idem pour 5...;
pour R = 2 et son Pi =7 , on part de 2 qui est déjà marque 0 et on marque tous les nombres par pas de 7...

puis pour  R = 9 et son Pi = 11, on part de 9 ou neuvième entier, qui lui aussi est marqué 0, on marque tous les nombres par pas de 11...

pour le dernier R =6 avec Pi = 13, on part du 6ème entier marqué 0 , et on marque tous les nombres par pas de 13 ...fin du crible , on compte les 1...!

tu peux remarquer que c'est Eratosthène mais dans les congruences....! d'où [tex]\pi(n)[/tex] vaut [tex]\frac{n}{Ln. n}[/tex] lorsque la lim n tends vers + l'infini...

Et: [tex]G(n)[/tex] la fonction qui compte les 1, de 1 à n vaut [tex]\frac{n}{Ln. 2n}[/tex] lorsque la lim n tends vers + l'infini... Car on crible avec les Pi <= sqrt de 2n et non de n.... Mais jusqu'à la lim n

C'est relativement simple....non ?

Dernière modification par LEG (23-10-2020 10:28:59)

Hors ligne

#10 21-01-2018 18:29:20

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

Re : crible en python

Salut,

Non, je n'ai pas compris grand chose, je vais devoir prendre un exemple et le faire à la main...
J'ai repris tout le programme et l'ai testé avec l'IDLE de Python.
Sortie :
(j'ai demandé l'affichage de la liste premiers fournie par eratostene)

[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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

√2N = 44
> On prend N = 1000 , donc 2N = 2000
> Pi(2N) = 303
> Estimation du TNP Pi(2N) = 2N/log(2N) = 263.12664984790376
> Estimation Pi(2N) = N/log(N)+ N/log(2N) = 276.32815222503586
> Estimation Pi(2N)-Pi(N) = N/log(2N) = 131.56332492395188
> Avec eratostene: On compte 168 nombres premiers entre 1 et 1000
> Avec eratostene: On compte 135 nombres premiers entre 1000 et 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

Si je teste, en partant de n=1000 :
n=int((2*n)**0.5)
le prog me sort

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
√2N = 44
> On prend N = 1000 , donc 2N = 2000
> Pi(2N) = 18
> Estimation du TNP Pi(2N) = 2N/log(2N) = 263.12664984790376
> Estimation Pi(2N) = N/log(N)+ N/log(2N) = 276.32815222503586
> Estimation Pi(2N)-Pi(N) = N/log(2N) = 131.56332492395188
> Avec eratostene: On compte 18 nombres premiers entre 1 et 1000
> Avec eratostene: On compte 0 nombres premiers entre 1000 et 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

Tu constates qu'il y a un gros souci si on limite les calculs à [tex] E(\sqrt{2n})[/tex]...
J'ai testé avec ma version eratosthene (sans oublier le h cette fois) : même souci...

Réfléchis donc à ce problème : je t'ai fourni les listes de premiers dans les deux cas fournies soir par eratostene original soit par eratosthene (ma version) : ce sont strictement les mêmes listes...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#11 21-01-2018 19:30:01

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

Re : crible en python

yoshi a écrit :

Salut,

Non, je n'ai pas compris grand chose, je vais devoir prendre un exemple et le faire à la main...

Tu constates qu'il y a un gros souci si on limite les calculs à [tex] E(\sqrt{2n})[/tex]...
J'ai testé avec ma version eratosthene (sans oublier le h cette fois) : même souci...

Réfléchis donc à ce problème : je t'ai fourni les listes de premiers dans les deux cas fournies soir par eratostene original soit par eratosthene (ma version) : ce sont strictement les mêmes listes...

@+

Non il n'y a pas de souci je pense que l'on ne c'est pas compris.

le but ce n'est pas d'extraire les nombres premiers de 1 à n avec Eratosthène, ni même de savoir combien qu'il y en a de n à 2n avec eratosthne, c'est le crible _G qui compte.
Car lui, il crible les entiers de 1 à n qui sont congrus à 2n (mod Pi) ceux qui donnera les nombres premiers de n à 2n.
Et pour ce faire, il a besoin uniquement des nombres premiers Pi d 'Eratosthène inférieur à racine de 2n, c'est à dire : [tex] E(\sqrt{2n})[/tex]..
C'est bien pour cela que le criblage par Eratosthène jusqu'à n ou 2n ne me sert à rien , par contre j'ai besoin des Pi,  [tex] E(\sqrt{2n})[/tex] pour le crible _ G

Au début mon petit fils à utilisé E ratosthène jusqu'à n et 2n afin de vérifier si il n'y avait pas d'erreur dans crible_G ...et je pensais qu'ensuite il avait limité le crible d'Ératosthène à [tex] E(\sqrt{2n})[/tex]...

je vais donc essayer de modifier la ligne 4 par ta ligne : n=int((2*n)**0.5) et voir si cela marche...mais je pense qu'il faut modifier d'autre ligne...

Dernière modification par LEG (23-10-2020 10:37:27)

Hors ligne

#12 21-01-2018 19:54:39

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

Re : crible en python

voila le test jusqu'à n= 600 000 000 mais avec cribl_mod 30:
crible _g: temps mis en secondes :
initialisation: 1",67
criblage des entiers de 1 à n : 213".89
extraction des premiers de n à 2n : 30",15
il y en a : 29 130 002

crible_mod30
initialisation: 7".39
famille de chaque Pi :187",85 ('c'est la recherche et la position de départ des restes R et leur Pi, par famille)
criblage des 8 familles de 1 à n : 34",71
extraction des premiers de n à 2n : 15",83
il y en a : 29 130 002

maintenant je fais le test avec Crible _G uniquement  en espérant qu'eratosthène ne va pas cribler au dela de Sqrt de 2n...
donc je vais voir combien de temps il met..
a tout de suite

Dernière modification par LEG (22-01-2018 10:40:01)

Hors ligne

#13 21-01-2018 20:15:28

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

Re : crible en python

il met un peu plus de 4' mais en plus il ne trouve pas le même nombre de premiers de n à 2n il en trouve 29 130 002.....???? il y a un hic.
dans cette version ....

je vais remettre ta ligne 4 :n=int((2*n)**0.5)

Dernière modification par LEG (21-01-2018 20:54:39)

Hors ligne

#14 21-01-2018 20:27:26

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

Re : crible en python

Bonsoir Yoshi et merci, je pense que cette ligne et bonne , et je ne touche pas au reste ...si tu as une autre idée...passe une bonne soirée...

Hors ligne

#15 21-01-2018 20:59:31

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

Re : crible en python

Heureusement que je viens de vérifier avec l'algo nb premier , il y a bien 29130002 premiers de n à 2n donc la ligne 4 n=int((2*n)**0.5) génère une erreur dans les deux crible,G et mod 30....A+

Hors ligne

#16 22-01-2018 08:10:33

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

Re : crible en python

Salut,


Ce qui m'avait faut sursauter et à quoi visiblement tu n'as pas prêté attention, c'était ça :
> Avec eratostene: On compte 18 nombres premiers entre 1 et 1000
> Avec eratostene: On compte 0 nombres premiers entre 1000 et 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

le but ce n'est pas d'extraire les nombres premiers de 1 à n avec Eratosthène, ni même de savoir combien qu'il y en a de n à 2n avec eratostene, c'est le crible _G qui compte

Pourtant,
avec ta fonction eratostene, voilà la liste premiers fournie :
[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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Avec ma fonction eratosthene qui est bien le crible d'eratosthène, voilà cette fois la liste premiers fournie
[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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Résultats parfaitement identiques. Alors pourquoi dis-tu que "le but ce n'est pas d'extraire les nombres premiers de 1 à n avec Eratosthène", c'est pourtant ce que fait ta fonction eratostene...

Ta ligne n=int(n) ne fait juste que convertir n en un nombre entier au cas où on ait entré un décimal.
D'ailleurs si je tape "ABC" en entrée, joli message d'erreur...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#17 22-01-2018 09:08:34

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

Re : crible en python

yoshi a écrit :

Salut,

Ce qui m'avait faut sursauter et à quoi visiblement tu n'as pas prêté attention, c'était ça :
> Avec eratostene: On compte 18 nombres premiers entre 1 et 1000
> Avec eratostene: On compte 0 nombres premiers entre 1000 et 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

le but ce n'est pas d'extraire les nombres premiers de 1 à n avec Eratosthène, ni même de savoir combien qu'il y en a de n à 2n avec eratostene, c'est le crible _G qui compte

Pourtant,
avec ta fonction eratostene, voilà la liste premiers fournie :
@+

Re
je vois que tu n'as pas saisi le but du programme . On a besoin d'Eratosthène pour faire fonctionner crible_G ou crible_mod 30, afin qu'Eratosthène extrait les nombres premiers [tex]P_i\leqslant\sqrt{2n}[/tex]

crible_G marque les entiers de 1 à n qui sont [tex]\equiv {2n}[P_i][/tex] ce qui ensuite donne le nombre de premiers  [tex]q [n ; 2n] [/tex] . d'où, 135 entiers [tex]e\equiv{2000}[P_i][/tex] [tex]= 135[/tex] premiers [tex]q [1000 ; 2000][/tex].

Donc on calcul les restes R de 2n par les  [tex]P_i[/tex] , ensuite on part de R et on marque les entiers tous les  [tex]P_i [/tex] nombres jusqu'à la lim n , donc avec chaque couple  [tex]R + P_i [/tex].

le but d'eratosthene est d'extraire ces  [tex]P_i [/tex] pour faire fonctionner le programme crible_G ou mod30 ce que tu as dans la deuxième partie du programme à partir de la ligne 53
:


def crible_G(n):
  nombres = n*[1]
  nombres[0] = 0
  p = eratostene(math.sqrt(2*n))
  lenp = len(p)
  r = []
  for i in range(lenp):
 

j'ai bien vue ce que tu m'indiques:

> Avec eratostene: On compte 18 nombres premiers entre 1 et 1000
> Avec eratostene: On compte 0 nombres premiers entre 1000 et 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

Mais est ce que tu as extrait les 135 premiers de 1000 à 2000 en utilisant crible_G , car si c'est le cas c'est ce que je veux effectivement, mais les 18 premiers extrait par Eratosthène, ne sont pas les [tex]P_i\leqslant\sqrt{1000}[/tex] ni les [tex]P_i\leqslant\sqrt{2000}[/tex], ce qui n'est pas pareille....! car on a 11 [tex]P_i\leqslant\sqrt{1000}[/tex]; et 14[tex]P_i\leqslant\sqrt{2000}[/tex].

Dernière modification par LEG (08-09-2018 09:37:16)

Hors ligne

#18 22-01-2018 12:11:52

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

Re : crible en python

Bonjour,

Les listes fournies font suite à ta remarque : "Le but de ... n'est pas..."...
J'ai répondu à la question (que tu n'as pas posée) :
que fait la fonction eratostene() ?
En utilisant ma propre fonction, eratosthene qui, elle, a été construite pou être un crible d'eratosthene, j'ai comparé les résultats de l'une et de l'autre.
Les résultats fournis en sortie par l'une ou l'autre, bruts de décoffrage (rôle de la mention return premiers, montrent que ta fonction ou la mienne renvoient la même liste de nombres premiers inférieurs à 1000 (si n =1000), inférieurs à 44 (si n = 44).

Voilà le programme qui me sert à mes essais et notamment à établir les deux listes fournies dans mon dernier post et l'affichage du post #10 (où je n'avais pas ces lignes :

print ("Avec ta fonction eratostene :")
print(eratostene(1000))

print("\nAvec ma fomction eratosthene qui est bien le ctible d'eratosthène")
print (eratosthene(1000))

ni le # devant la dernière ligne. Y est intégrée ma fonction eratosthene (avec le h).
Le # indique une remarque, le programme ne tient pas compte de la ligne
Si j'utilise ma fonction erato, partout où il est est écrit erastotene, je rajoute un h entre le t et le e

import math

def eratosthene(n):
    nombres, premiers = [],[]
    # n=int((2*n)**0.5)
    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

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*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 eratostene: On compte " + str(len(liste1)-compte) + " nombres premiers entre 1 et " + str(n))
  print("> Avec eratostene: 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)


def crible_G(n):
  nombres = n*[1]
  nombres[0] = 0
 
  p = eratostene(n)
  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(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)
  return premiers

#n = int(input("Donnez la valeur de N : "))
n=1000
print ("Avec ta fonction eratostene :")
print(eratostene(1000))

print("\nAvec ma fomction eratosthene qui est bien le ctible d'eratosthène")
print (eratosthene(1000))

#premiersNa2N(n)

Je t'ai dit simplement que j'appelle :
eratostene (1000) ou eratosthene(1000), les deux fonctions me fournissent la même liste des nombres premiers inférieurs à 1000 (ou à 44 si j j'enlève le # devant n=int((2*n)**0.5) : 44 = partie entière de [tex]\sqrt{2000}[/tex]).

Si je supprime les lignes ajoutées et le # devant la dernière ligne, que je remets un # devant n=int((2*n)**0.5), je lance le programme, affichage (cohérent) que ce soit avec la fonction eratostene ou la mienne eratosthene :

√2N = 44
> On prend N = 1000 , donc 2N = 2000
> Pi(2N) = 303
> Estimation du TNP Pi(2N) = 2N/log(2N) = 263.12664984790376
> Estimation Pi(2N) = N/log(N)+ N/log(2N) = 276.32815222503586
> Estimation Pi(2N)-Pi(N) = N/log(2N) = 131.56332492395188
> Avec eratostene: On compte 168 nombres premiers entre 1 et 1000
> Avec eratostene: On compte 135 nombres premiers entre 1000 et 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

Par contre, si j'utilise n= int((2*n)**0.5) dans la fonction eratostene ou la mienne eratosthene, j'obtiens l'affichage qui m'a fait sursauter :

√2N = 44
> On prend N = 1000 , donc 2N = 2000
> Pi(2N) = 18
> Estimation du TNP Pi(2N) = 2N/log(2N) = 263.12664984790376
> Estimation Pi(2N) = N/log(N)+ N/log(2N) = 276.32815222503586
> Estimation Pi(2N)-Pi(N) = N/log(2N) = 131.56332492395188
> Avec eratostene: On compte 18 nombres premiers entre 1 et 1000
> Avec eratostene: On compte 0 nombres premiers entre 1000 et 2000
> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

qui me montre que n= int((2*n)**0.5) produit selon moi des résultats incohérents, que ce n'est pas ce qu'il faut faire.

En résumé, je n'ai pas du tout cherché à entrer dans les méandres ultérieures du prog.
Je me suis concentré et consacré exclusivement sur le  résultat que renvoie la fonction eratostene avec return premiers, une liste de nombres premiers et que si je modifie le n dans les fonctions eratostene ou eratosthene, la sortie renvoie des choses incohérentes et que ce n'est pas cela (ou pas seulement) qu'il faut faire...


Et qu'en conséquence, il va me falloir du temps pour comprendre ce que fait ce programme non documenté.
Et là, j'ai un autre gros fer au feu prioritaire (mettre à jour le site internet de mon association)...
J'en suis désolé pour toi, mais tant que je n'aurais pas fait à la main pas à pas ce que fait le prog, tex explications resteront pour moi des phrases creuses : je touche probablement là  aux limites de mon intelligence...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#19 22-01-2018 14:16:58

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

Re : crible en python

yoshi a écrit :

Bonjour,

Les listes fournies font suite à ta remarque : "Le but de ... n'est pas..."...
J'ai répondu à la question (que tu n'as pas posée) :
que fait la fonction eratostene() ?

La fonction Eratosthène doit extraire les nombres premiers [tex]P_i\leqslant\sqrt{2n}[/tex] donc [tex]P_i\leqslant\sqrt{2000} = 44[/tex]
c'est tout ce qu'elle doit faire, pour utiliser ces [tex]P_i\leqslant 44[/tex] dans la fonction du crible _G...ci dessous

   
def crible_G(n):
  nombres = n*[1]
  nombres[0] = 0
 
  p = eratostene(n)
  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(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)
  return premiers

#n = int(input("Donnez la valeur de N : "))
n=1000
print ("Avec ta fonction eratostene :")
print(eratostene(1000))

print("\nAvec ma fomction eratosthene qui est bien le ctible d'eratosthène")
print (eratosthene(1000))

#premiersNa2N(n)

Je t'ai dit simplement que j'appelle :
eratostene (1000) ou eratosthene(1000), les deux fonctions me fournissent la même liste des nombres premiers inférieurs à 1000 (ou à 44 si j j'enlève le # devant n=int((2*n)**0.5) : 44 = partie entière de [tex]\sqrt{2000}[/tex]).

Ok

Si je supprime les lignes ajoutées et le # devant la dernière ligne, que je remets un # devant n=int((2*n)**0.5), je lance le programme, affichage (cohérent) que ce soit avec la fonction eratostene ou la mienne eratosthene :

Ce qui est logique, puisque Eratosthène va cribler jusqu'à n et 2n, étant donné qu'il n'est pas limité à la [tex]\sqrt{2n}[/tex]

Par contre, si j'utilise n= int((2*n)**0.5) dans la fonction eratostene ou la mienne eratosthene, j'obtiens l'affichage qui m'a fait sursauter :

Je pense que l'explication est : Eratosthène ne crible pas jusqu'à n ni jusqu'à 2n; mais uniquement jusqu'à la racine de 2n pour utiliser ces nombres premiers dans le crible_G, donc il extrait bien les premiers [tex]P_i\leqslant 44[/tex].

car comme tu l'as remarqué, le crible _G a bien criblé les congruents à Pi puisqu'il donne bien 135 premiers de 1000 à 2000

> Avec goldbach: On compte 135 nombres premiers entre 1000 et 2000

donc le résultat d'Eratosthène on ne s'en occupe pas, et il faut  mettre # devant les lignes concernées afin qu'il n'écrive pas le résultat...

qui me montre que n= int((2*n)**0.5) produit selon moi des résultats incohérents, que ce n'est pas ce qu'il faut faire.

c'est peut être le cas...Mais si je lance mon programme et que je modifie la ligne n = int(n) par la tienne  n= int((2*n)**0.5). je n'obtient pas les bonnes valeurs  pour 1000 oui mais pour 30 000 000 voila les vraies valeurs:1 704 256 entre 30 000 000 et 60 000 000


Je te remercie de ton implication.

je vais changer la valeur de la ligne 4 ,  je refais le test jusqu'à 30 000 000 le résultat obtenu est :3 440 913 , c'est à dire le double..???

Ps: j'ai copié ton programme que j'ai collé dans pycharme je n'arrive pas à le lancer ....avec mon appli ...
@+

Dernière modification par LEG (23-10-2020 10:45:58)

Hors ligne

#20 22-01-2018 14:30:26

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

Re : crible en python

Autrement dit lorsque l'on modifie la ligne 

n = int[n]  

par :

 n=int((2*n)**0.5)

cela ne peut pas marcher car on devrait avoir pour n = 1000, 2n = 2000;  [tex]\sqrt {2000}[/tex], 14 premiers < 44, et non 18...

il y a peut être une solution:
demander à Eratosthène de cribler jusqu'à sqrt de n, et pour crible _g  jusqu'à n....rentrer deux valeur de n = 44 pour Eratosthène , et 1000 pour crible_G
ou alors il faut que Eratosthène crible bien uniquement jusqu'à la partie entière de  [tex]\sqrt {n}[/tex] et on rentre bien la valeur de n au départ...
bonne journée

Hors ligne

#21 22-01-2018 14:35:59

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

Re : crible en python

voici le lien pour les tests cribl_G et crible_mod30 avec les temps en seconde .
https://www.cjoint.com/c/HAwnHvbeTpW

Hors ligne

#22 22-01-2018 15:05:32

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

Re : crible en python

Re,

Mon programme = ?
La totalité ou seulement la fonction eratosthene (celle avec un h) ?
Si c'est la totalité de ce que j'au posté, c'est inutile : c'est ton prog + ma fonction...
Au passage eratostene est presque 3 x plus raide que eratosthene...

je n'arrive pas à le lancer

Qu'est-ce que tu entends par là ?
Tu n'as juste qu'à copier les lignes depuis
def eratosthene(n):
jusqu'à
return premiers
et à coller la fonction copiée soit avant la def eratostene(n), soit après dans ton prog... Et ton prog fonctionnera comme avant parce qu'une fonction ne se lance pas, elle est là et ne réagit que si on l'appelle, par ex :
Prem1 = eratostene(n)
print (Prem1)                                       là on l'affiche : tout dépend la valeur de n, ça risque d'être trèe lon
Prem2 = eratosthene(n)
print (Prem2)
Dans le cas contraire, c'est comme si elle n'existait pas...
Il n'y aucune raison que Pycharm ne fasse pas fonctionner un prog écrit chez moi...
[Parenthèse]
En référence à : http://www.bibmath.net/forums/viewtopic.php?id=5011
J'avais écrit :

#!/usr/bin/python
# -*- coding: UTF-8 -*-

def titre():
    print ("        *****************************")
    print ("        **                         **")
    print ("        **  Produit de codes CLE   **")
    print ("        **                         **")
    print ("        *****************************")
    print ()
    print ()
    print ()

def cle(a,l):
    code=[]
    for i, char in enumerate(a):
        if char>"0":
            code.append(l-i-1)
    return code

   
## Nombres dont on doit trouver le Code CLE ##

nb = [123125256,768648254]

#############################################
titre()
Codes=[]
print("            +-+ Recherche des codes CLE +-+\n")
for n in range(2):
    print("   ## Nombre n°",n+1)
    code=[]
    a=bin(nb[n])[2:]
    print ("Le nombre "+str(nb[n])+" en base 10")
    long=(8+len(str(nb[n])))//2
    esp=" "*long
    print (esp+"s'écrit donc")
    print (a+" en base 2")
    print ()
    print ("Son code CLE est :")
    l=len(a)
    print(str(nb[n])+"(",end="")
    code=cle(a,l)
    l=len(code)
    Codes.append(code)
    for i, char in enumerate(code):
        print(char,end="")
        if i<l-1:
            print (",",end="")
    print(")"+"\n\n")
   
print("            +-+ Produit des codes CLE +-+\n")
Prod_codes,Prod, Traite=[],[],[]
fin=max(Codes[0])+max(Codes[1])+8
Lst_nb_puiss=[0]*fin
for i in Codes[0]:
    for j in Codes[1]:
        Lst_nb_puiss[i+j]+=1
        Prod_codes.append(i+j)
print ()
print(Lst_nb_puiss,"\n")
Prod_codes.sort(reverse=True)    
print ("    *** BRUT ***")
print (Prod_codes,"\n")
for a,nb_a in enumerate(Lst_nb_puiss):
    if nb_a<2:
        pass
    else:  
        n_bin=bin(nb_a)[2:]
        lg=len(n_bin)
        code=cle(n_bin,lg)
        Lst_nb_puiss[a]= 0
        for i in code:
            Lst_nb_puiss[a+i]+=1
           
fin-=1
for a in range(fin,-1,-1):
    nb_a=Lst_nb_puiss[a]
    if nb_a>0:
        Prod.append(a)
       
print ("    *** FINAL ***")
print(Prod,"\n")
P=0
print ("Le nombre correspondant à ce code CLE est :")
for i in Prod:
    P+=2**i

print (P,"\n")
print ("Vérification :" )
print (nb[0],"*",nb[1],"=",nb[0]*nb[1])

Ce programme doit fonctionner sur Pycharm aussi.
Je le testerai plus tard avec. Je vais retourner à ma mise à jour...
[/Parenthèse]

Je t'ai déjà demandé, c'est Pycharm qui a décidé d'une indentation de 2 caractères, alors que c'est 4 recommandé ?
Moi je travaille avec 4, peut-être que Pycharm n'aime pas le mélange des deux ?
Il faut que j'aille voir...
Je viens de le charger, j'ai regardé vite fait les exemples du site.
J'ai une réponse : l'indentation standard de Pycharm est bien de 4 caractères...
Alors pourquoi 2 ? Choix délibéré du petit-fils ? Dans ce cas mauvaise idée pour la lisibilité...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#23 22-01-2018 15:39:04

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

Re : crible en python

yoshi a écrit :

Re,

Mon programme = ?
La totalité ou seulement la fonction eratosthene (celle avec un h) ?

au début la totalité, puis

j'ai copié ceci à la place de la mienne jusqu'à return premier :

def eratosthene(n):
    nombres, premiers = [],[]
    # n=int((2*n)**0.5)
    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
 

je n'arrive pas à le lancer

Qu'est-ce que tu entends par là ?

le fenêtre dos , apparait, je rentre la valeur n = 30000000, puis entrée..
la fenêtre se ferme..

           

Ce programme doit fonctionner sur Pycharm aussi.
Je le testerai plus tard avec. Je vais retourner à ma mise à jour...
[/Parenthèse]

ok

Je t'ai déjà demandé, c'est Pycharm qui a décidé d'une indentation de 2 caractères, alors que c'est 4 recommandé ?

Aucune idée..., je lui ai demandé de cribler avec eratosthène uniquement jusqu'à [tex]\sqrt{2n}[/tex], ce qu'il n'a pas fait...

Moi je travaille avec 4, peut-être que Pycharm n'aime pas le mélange des deux ?
Il faut que j'aille voir...
Je viens de le charger, j'ai regardé vite fait les exemples du site.
J'ai une réponse : l'indentation standard de Pycharm est bien de 4 caractères...
Alors pourquoi 2 ? Choix délibéré du petit-fils ? Dans ce cas mauvaise idée pour la lisibilité...

je ne saurait te répondre car pour moi c'est le brouillard total...., et je ne sais pas pourquoi il a fait ce choix...je vais essayer de t'expliquer ce que doit faire le programme complet post suivant...

@+

Hors ligne

#24 22-01-2018 16:38:16

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

Re : crible en python

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 ?

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


Arx Tarpeia Capitoli proxima...

Hors ligne

#25 22-01-2018 17:03:08

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

Re : crible en python

ton dernier post de 16h38 : effectivement je n'avais pas compris que tu parlais du h d'Eratosthène

est ce que ça veut dire que dans mes deux programme "Pycharme " il faut que je mette le h dans tous les Eratosthène, où il ne figure pas...et ensuite ...?

que dois faire le programme :
on rentre la valeur n,
on fait appel à eratosthène pour cribler de 1 à [tex]\sqrt{2n}[/tex] pour obtenir les premiers [tex]P_i\leqslant\sqrt{2n}[/tex] qui vont être utilisé par le crible_G à partir de la:

def crible_G(n):
  nombres = n*[1]
  nombres[0] = 0
  p = eratostene(math.sqrt(2*n))
  lenp = len(p)
  r = []
  for i in range(lenp):

..etc..

le programme fait la liste des entiers naturels de 1 à n , représenté par des 1
exemple n = 1000:

11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 .......jusqu'à n

donc chaque 1 est un entier  1,2,3........n.

eratosthène à extrait les premiers [tex]P_i\leqslant\sqrt{2n}[/tex] donc < à 44.
soit la liste des $P_i$ : {2.3.5.7.11.13.17.19.23.29.31.37.41.et 43}

le crible_g va utiliser ces $P_i$ : pour calculer le reste R de 2000 par chaque $P_i$ .
Soit les R = {0.2.0.5.9.11.11.5.22.28.16.2.32 et 22}

le crible _g va donc cribler les entiers représentés par 1, $\equiv{2n} [P_i]$ selon le même principe qu'Ératosthène , mais en partant du reste R de 2n Par Pi. On marquera donc tous les entiers non nul de 1 à n, qui sont égaux modulo Pi avec 2n , c'est à dire qui partagent le même reste R modulo Pi

("si il n'y a pas R = 1, alors 2n -1 est premier, donc le premier 1 ne peut être remplacé par 0 et de la même façon si R = 0 on part directement de $P_i$")
sinon on part  de R.
le premier couple R + P_i est : (0 ; 2) on part donc du deuxième entier = $P_i = 2$ que l'on marque 0, puis tous les 2 nombres...

10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101......jusqu'à n

le deuxième couple R + P_i est : (2 ; 3) on marque donc le deuxième entier d'un 0, puis tous les 3 nombres...

101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000......jusqu'à n

le troisième couple R + P_i est : (0 ; 5) on part donc du cinquième entier =$ P_i = 5$ que l'on marque 0, puis tous les 5 nombres

1010001010001000001010000100000100010100010100010000010100001000001000101000101000100000101000001000101000101000100000101000001000101000101000100000101000001000101000......jusqu'à n

le quatrième couple R + P_i est : (5;7) on part donc du cinquième entier que l'on marque 0, puis tous les 7 nombres

1010001010001000000010000000000100010100010100010000000100000000001000101000101000100000001000001000100000101000100000101000001000101000001000100000100000001000101000......jusqu'à n

le cinqième couple R + P_i est : (9;11) on marque donc le neuvième entier d'un 0, puis tous les 11 nombres

1010001000001000000010000000000100010100000100010000000100000000001000101000101000100000001000000000100000101000100000001000001000101000001000100000100000001000101000......jusqu'à n

....etc...
A la fin on compte les 1 les entiers qui ne sont congrus à 2n mod P_i, donc: qui donnent les nombres premiers q entre 1000 et 2000
puisque si un entier A de 1 à n est non congrus à 2n[Pi], il ne partage pas le même reste R avec 2n, par conséquent Pi ne divise pas cette différence tel que 2n - A, alors 2n - A est un nombre premier q . Tout entier < 2n,  non divisible par un nombre premier Pi < racine de 2n, est un nombre premier : selon Ératosthène.

C'est tout simplement le crible d'eratosthène mais dans les congruences , au lieu de partir de P_i pour barrer leurs multiples, on part de R et on barre tous les congruents de P_i....Voila....

Dernière modification par LEG (23-10-2020 11:03:51)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
trente et un moins six
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