Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#26 22-01-2018 18:27:19
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 ?
ok donc il faudrait que je remplace la première fonction d'eratostène sans h , par la tienne ci dessous
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 ? :
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 18:42:09
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 19:16:18
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 19:36:19
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 14:41:41
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 07:02:19
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour
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 09:15:05)
Hors ligne
#32 26-01-2018 20:01:33
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 11:07:41
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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...
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 11:21:09)
Hors ligne
#34 27-01-2018 11:46:56
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
suite du post ci-dessus , si j'ai bien suivi ton exemple
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...?
# 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 13:07:51
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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:
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:
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 13:47:28
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 15:46:10
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 16:07:00)
Hors ligne
#38 27-01-2018 16:10:25
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 18:05:31
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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")
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 18:26:02)
Hors ligne
#40 27-01-2018 18:24:14
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
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 19:27:35
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 22:23:16
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 :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 22:55:27)
Hors ligne
#43 28-01-2018 17:08:14
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 12:13:03)
Hors ligne
#44 29-01-2018 18:48:44
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 12:13:25)
Hors ligne
#45 29-01-2018 20:45:42
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 07:50:20
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 12:57:42
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 12:13:48)
Hors ligne
#48 15-03-2018 11:29:20
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 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 11:32:50)
Hors ligne
#49 16-03-2018 15:59:18
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
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 16:43:26
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
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 12:14:43)
Hors ligne