Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#301 23-10-2018 22:01:02
- leg.01
- Invité
Re : crible en python
Bonjour Yoshi
1) c'est exact, mais je ne pouvais pas modifier l'erreur de la ligne :
# On crible directement à partir de l'index avec pi
par rapport au message #296
donc tu peux supprimer le #299.
2) Mais, le nouveau code dans son intégralité a bien été publié #293.
avec cette phrase erronée "# on crible directement avec le reste "
Pour ta question personnelle , ce n'est pas moi qui vais te dire le contraire car j'ai du mal à digérer que les programme doivent être écrit en anglais, alors que la langue Française est largement plus riche en nuances... que cette langue pourrie....! Ca n'engage que moi...!
Il en est de même des démonstrations Mathématique qui doivent être publiées en anglais et non dans la langue du pays d'origine.
Jusqu'à preuve du contraire c'est pas les anglais qui ont découvert les Mathématiques , ni le fil à couper le beurre.....
#302 08-12-2018 22:18:49
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour
Alors @Yoshy ...du boulots..
voila le programme fait en C++ par une âme charitable de l'univ - grenoble-Alpes
il envoie et j'ai testé pour N = 60 mds temps 120 secondes
je te met le programme car je dois bien ça sur ton forum...
// -*- compile-command: "/usr/bin/g++ -g goldbachs.cc" -*-
#include <vector>
#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <time.h>
using namespace std;
// fill Erathosthene sieve crible for searching primes up to 2*crible.size()*32+1
// crible is a (packed) bit array, crible[i] is true if 2*i+1 is a prime
// crible must be set to true at startup
void fill_crible(vector<unsigned> & crible,unsigned p){
crible.resize((p-1)/64+1);
unsigned cs=crible.size();
unsigned lastnum=64*cs;
unsigned lastsieve=int(std::sqrt(double(lastnum)));
unsigned primesieved=1;
crible[0] = 0xfffffffe; // 1 is not prime and not sieved (2 is not sieved)
for (unsigned i=1;i<cs;++i)
crible[i]=0xffffffff;
for (;primesieved<=lastsieve;primesieved+=2){
// find next prime
unsigned pos=primesieved/2;
for (;pos<cs;pos++){
if (crible[pos/32] & (1 << (pos %32)))
break;
}
// set mutiples of (2*pos+1) to false
primesieved=2*pos+1;
unsigned n=3*primesieved;
for (;n<lastnum;n+=2*primesieved){
pos=(n-1)/2;
crible[(pos/32)] &= ~(1<<(pos %32));
}
}
}
unsigned nextprime(vector<unsigned> & crible,unsigned p){
// assumes crible has been filled
++p;
if (p%2==0)
++p;
unsigned pos=(p-1)/2,cs=crible.size()*32;
if (2*cs+1<=p)
return -1;
for (;pos<cs;++pos){
if (crible[pos/32] & (1<<(pos%32))){
pos=2*pos+1;
// if (pos!=nextprime(int(p)).val) CERR << "error " << p << endl;
return pos;
}
}
return -1;
}
typedef unsigned long long ulonglong;
size_t GCrible(const vector<ulonglong> & premiers,ulonglong n,int fam){
int cl=clock();
size_t lencrible=n/30,nbpremiers=premiers.size();
vector<bool> crible(lencrible,true);
ulonglong n2=2*n;
vector<ulonglong> indices(nbpremiers);
for (size_t i=0;i<nbpremiers;++i){
ulonglong p=premiers[i];
ulonglong reste=n2 % p;
if (reste %2==0)
reste += p;
ulonglong pi2=2*p;
while (reste %30!=fam)
reste += pi2;
reste /= 30;
indices[i]=reste;
}
ulonglong nslices=lencrible/3000000,currentslice=0;
if (nslices==0) nslices=1;
for (;currentslice<nslices;++currentslice){
size_t slicelimit=currentslice+1;
slicelimit=slicelimit==nslices?lencrible:(currentslice+1)*(lencrible/nslices);
for (size_t i=0;i<nbpremiers;++i){
ulonglong p=premiers[i];
size_t index;
for (index=indices[i];index<slicelimit;index+=p)
crible[index]=0;
indices[i]=index;
}
}
size_t total=0;
for (size_t index=0;index<lencrible;++index)
total += int(crible[index]);
cout << "Nombre premiers criblés famille " << fam << " entre "<< n << " et " << n2 <<": " << total << " time " << (clock()-cl)*1e-6<< endl;
return total;
}
int main(int argc,char ** argv){
vector<unsigned> crible;
ulonglong N;
int fam=1;
if (argc>1){
N=atoll(argv[1]);
if (argc>2)
fam=atoi(argv[2]);
}
else {
cout << "Syntaxe " << argv[0] << " N fam. Donnez N puis fam: " ;
cin >> N;
cin >> fam;
}
double sqrt2N=unsigned(std::sqrt(2*double(N)));
fill_crible(crible,sqrt2N);
vector<ulonglong> premiers;
for (ulonglong p=7;p<=sqrt2N;){
premiers.push_back(p);
p=nextprime(crible,p);
if (p==unsigned(-1))
break;
}
GCrible(premiers,N,fam);
cin>>N;
}
installer codeblocks sous windows (selectionner le setup codeblocks + mingw pour installation)
Puis File>New>Empty File
puis Build>Compile et Run
Passe une bonne soirée A+
Cordialement LEG
Dernière modification par LEG (11-12-2018 09:47:08)
Hors ligne
#303 10-12-2018 09:15:23
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour
j'ai un petit souci: le but étant d'avoir deux cribles équivalents; pour cribler de N à 2N "Goldbach" et de 7 à N "Eratosthène" :
Afin de justifier les deux fonctions relatives à $\pi(n)$ et $G(n)$ : $\frac{n}{log . n}$ et $\frac{n}{log . (2n)}$
Voici la partie que je voudrai modifier pour utiliser GCrible de Goldbach dans Ecrible Eratosthène :
Voici la partie du progr origine que je dois modifier:
1) On remplacera la première ligne de def eratostene
n = int((2*n)**0.5) par n = int(n**0,5)
*****************************
## V. 6.2 ##
def eratostene(n):
n = int((2*n)**0.5) ## ligne à modifier ##
m = (n-1) // 2
limite=1+n
b = [True]*m
premiers = [2]
for i,p in enumerate(range(3,limite,2)):
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
debut,pas=j,2*i+3
for j in range(debut,m,pas):
b[j] = False
debut=i
for i in range(debut,m):
if b[i]:
premiers.append(p)
p += 2
#print(premiers)
return premiers[3:]
def CribleG3Y_mod30(n):
# INITIALISATION
global nombres,nbcell
start_i= time()
Primes_init = eratostene(n)
nn,nbcell = n*2,n//30
nombres = []
for i in range(1):
nombres.append([1]*nbcell)
P8 = {1:0} #pour 8 fam remettre les 8[1,7,...,29]
s_1=time()-start_i
print("Phase d'initialisation: %s seconds ---" % s_1)
# FAMILLES POUR CHAQUE Pi
start_time = time()
for i,pi in enumerate(Primes_init):
j = nn%pi
debut,fin,pas = j+pi*(1-j%2),min(pi*30,n),pi*2
Fam = [0] #pour 8 fam remettre les 8[0,0,...,0]
for j in range(debut,fin,pas):
if j%30 == 1: # changer le paramètre pour une fam choisie
fam = P8[1] # changer le paramètre pour une fam fxée , pour P8fam remettre [j%30]
if not Fam[fam]:
Fam[fam] = 1
debut_index = j//30
Nombres_fam = nombres[fam]
for index in range(debut_index, nbcell,pi):
Nombres_fam[index] = 0
s_23=time()-start_time
print("Bloc S2_s3 : %s seconds ---" % s_23)
#print(j)
#################################################################
Voici la partie que je veux modifier mais qui ne marche pas :
là on crible pareil, mais on n’a plus besoin de calculer le reste r de 2n par premiers…
Il faut par contre, une fonction tableMulti pour calculer le produit des 8 variables de vp = {a=31,b=7, c=11, d=13, e=17, f=19, g=23, h=29}
Par pi, et que l’on réitèrera. Pour chaque premier…
De sorte que le produit j = pi * vp , pour chaque premier , on calculera ensuite l’index…pour cribler ; au lieu du reste, dans Goldbach.
et ensuite que : j %30 == 1
exemple :
n = 3000 on a initialiser les 1 , 3000 /30 = 100, soit 100 cellules de 1
je prends premiers = 7
je calcule J = vp *7……….donc 8 produits au maximum, en vérifiant si j %30 == 1 car on crible la fam 1.
7*1 , 7*7, 7*11, 7*13 == 1%30 ; donc ok et je n’ai pas besoin d’aller jusqu’à pi = 29 pour calculer 7*29, d’accord….
Puis je vais calculer son index j = 91 , 91//30 = 3
Je positionne cellule 3 et je crible par pas de premiers = 7…de 3 à n//30 on remplace les [1] par [0] tous les 7 pas….etc… on réitère avec premiers = 11…..premiers <= sqrt de n et non de 2n, car c’est Eratosthène….modulo 30
**************************
le reste du programme, ne change donc pas.
Et ensuite je le ferai ...si possible...en C++ comme ci- dessus post d'hier .....
Dernière modification par LEG (12-12-2018 08:40:59)
Hors ligne
#304 10-12-2018 17:18:59
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : crible en python
Salut,
Encore une fois, tu tombes mal : décembre, mars, juin septembre sont des mois délicats puisque j'ai ma revue trimestrielle sur les bras...
Je m'apprêtai à te répondre vite fait sur le message d'erreur, quand j'ai vu : https://www.developpez.net/forums/d1920 … me-crible/, alors je me suis abstenu...
J'aurais répondu de toutes façon, la même chose.
Cela dit, je prends le risque d'être mauvaise langue, tu as déclaré :
- ne pas être le programmeur,
- que le prg est dû à ton petit-fils.
Alors tu as de fortes chances :
* de te faire renvoyer vers un tuto de Python,
* de te te faire renvoyer vers ton petit-fils...
Bonne chance
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#305 10-12-2018 20:12:57
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
ok @Yoshi
je comprend, mais je suis bien obliger de dire la vérité..je ne vais quand même pas m'octroyer un travail que je n'ai pas fais ..
Ceci dit, ça fait trois jours que je bataille pour modifier trois lignes du programme et je n'ai toujours pas trouver la réponse ...ni avec un ou des tutos Python, qui me font tourner en rond...à part me dire que l'on ne multiplie pas une liste par un nombre ou que c'est un tuple dont les valeur ne sont pas modifiable , C'est bien pour ça que je l'ai utilisé et comment on utilise les valeurs pour calculer le produit pour chaque premiers appelé..???? peau de balle et variété...
Merci quand même
cordialement
leg
Hors ligne
#306 10-12-2018 21:22:18
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : crible en python
Re,
Allez explique-toi quand même, en termes aussi clairs et précis que possible : pas le pourquoi tu veux faire ça, mais techniquement, que cherches-tu à faire avec tes tuples
Et si, on peut multiplier une liste ou un tuple par un nombre : [1,2,3]*3 --> [1, 2, 3, 1, 2, 3, 1, 2, 3] ; (1,2)*3 --> (1, 2, 1, 2, 1, 2)
Ou encore :
[(1,2)]*3 ---> [(1, 2), (1, 2), (1, 2)] ; [[1,2,3]]*3 ---> [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Mais ce n'est certainement pas ce que tu attends...
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#307 11-12-2018 07:52:20
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour @Yoshi
effectivement tu as parfaitement compris qu'avec ma list de 8 nombres premiers ce n'est pas ce que tu m'as indiqué..
voici ma liste de variables vp = 7,11,13,17,19,23,29,31 qui permet de calculer le produit de pi * vp
tu connais parfaitement le programme version "v 6.2# ci dessus, puisque tu me l'as fait...Donc à partir de la ligne :
la suite du programme ne changera pas on remplacera reste par produit soit :
Mais attention, on changera la première ligne de Eratosthène qui va cribler jusqu' la sqrt de n et non de 2n
Ce qui donnera par obligation :
def eratostene(n):
n = int(n**0.5)
En résumé, on va faire avec produit = vp * pi ce que l'on fait avec reste que, dans ton programme on a apelé j
C'est pour cette raison qu'il nous faut la liste des Pi $\leqslant \sqrt{n}$
*******************************************************************
on a entré:
n = 3000 et choisie la fam = 1 On part du carré de Pi
On a extrait les premiers avec ératostene < sqrt n et retourner les premiers[3:]
On a initialisé les 1 , 3000 /30 = 100, soit 100 cellules de 1
Exemple voila ce que cela donnerai à partir de la fonction
:
puis: on a vp [7 ; 31]
je prends pi = 7 ; J = a * b ; qui sont les variables Pi $\leqslant \sqrt{n}$
je calcule le produit j = a*b
a *7……….donc on peut avoir 8 produits au maximum, tant que le produit %30 != 1 car on crible la fam 1.
[7*7, 7*11, 7*13 == 1%30 ]; donc ok , le break est donné par 1%30 , je n’ai pas besoin d’aller jusqu’à b = 29 pour calculer 7*29, d’accord….
Puis je calcule son index: j = 91 , 91//30 = 3 index commun à a=7 et b=13
Que Je positionne cellule 3 et je crible par pas de premiers = 7…de 3 à n//30 on remplace les [1] par [0] tous les 7 pas….etc… on réitère avec b= 13, par pas de 13...de 3 à n//30.
On change d'index i +=1 relatif à pi = 11…..premiers $\leqslant \sqrt{n}$
[11*11 == 1%30 ]; ok
calcul de l'index :
j //30 = 4
que l'on positionne cellule 4, crible par pas de 11 de 4 à n//30 ...etc on réitère avec (i +=1) Pi = 13....
13*13 , 13*17,13*19,13*23,13*29,13*31, 13*37== 1%30 ok, position index = 16, crible par pas de 13 de 16....>n//30 ...puis par pas de 37....on réitère i +=1 avec Pi= 17 ...
[17*17, 17*19, 17*23 == 1%30 ]; ok position index = 13, crible par pas de 17de 13....>n//30 ...puis par pas de 23 ......> n//30...etc
i +1; pour Pi = a = 19
[a*a == 1%30 ] ; index = a²//30 = 12 ; crible par pas de 19 de 12 à n//30..
i+1 = 23 = a
[a*a ; a*29, a*31, a*37 , a*41, 23*47== 1%30 ] ; index = a*b //30 = 36 ; crible par pas de 23 de 36 à n//30.., puis par pas de 47 de 36 à n//30
etc...etc avec i incrémenté de 1 pour les a = 29,31,37,41,43,47,53...tant que tous les Pi <= à 53 n'ont pas exécuté leur criblage..Qui va s'arrêter à Pi = a = 47 :
29*29...index ....>n//30 par pas de 29
31*31...index ....>n//30 par pas de 31
i+=1 = a = 37 , qui lui à déjà criblé avec a = 13
a*a, a*41, a*43 ==1%30 ; index = a*b //30 = 53 ; crible par pas de 43 de 53 à n//30.., car 37 à déjà criblé jusqu'à n//30
43 à criblé
i+1 = a = 47
a*a ; a*53== 1%30 ; index = a*b //30 = 83 ; crible par pas de 53 de 83 à n//30 qui ne marque donc d'un [0],que la cellule:
47*53 = [0]....! Ce qui va très vite, les 13 a = Pi ont criblés. Fin de l'algorithme on fait la somme des [1] qui nous indique le nombre de premiers de 7 à n.
********************************************************************
On supprime donc les lignes en rapport avec 2n et /ou reste=2n%pi
Ce programme serra nommé ECrible , E pour Eratosthène mod30.
l'explication est : deux cribles:
E criblera par Famille les premiers de 7 à N.. la famille 1 où 1 n'est pas premier commencera à 31.
G criblera par famille de 1 à N en partant du reste et non du produit...car on crible les congruents de Pi...et non les multiples..etc, donc les premiers de N à 2N.
Ils ont la même propriété .!
d'où on peut affirmer que le nombre de nombres premiers G(n) de N à 2N vaut au minimum N / log 2N
par conséquent $pi(2n)$ vaut environ : [(N / log N) + (N / log 2N)] lorsque N tend vers + l'infini....
Dernière modification par LEG (21-12-2018 08:46:42)
Hors ligne
#308 11-12-2018 15:26:17
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : crible en python
Re,
Pas assez synthétique pour aller vite...
Déjà, là, ça commence mal :
1) je veux calculer le produit de chacun des éléments de list ,
Normalement, un matheux parle de produit de truc... par bidule : truc * bidule
J'ai relu 3 fois, rapidement il est vrai, et je n'ai toujours pas trouvé par quoi tu multiplies chaque élément de [7,11,13,17,19,23,29,31]...
Autre remarque Python est très (trop !) permissif. Ce que tu écris là ne devrait pas passer :
list = [7,11,13,17,19,23,29,31], parce que list est une fonction interne à Python, un mot "réservé", quoi.
list((1, 2, 3)) --> [1, 2, 3 ] transforme un tuple en liste.
Et dans l'autre sens : tuple([1, 2, 3 ]) --> (1, 2, 3)
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#309 11-12-2018 16:34:25
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
re: Je pensais qu'avec les exemples tu avais compris je modifie le #post 307
A ) on va remplacer les (restes de 2n par pi) et pour chaque premier <= sqrt de 2n..ok
enumeré par la fonction
B) on va calculer le produit de chaque élément de la liste des variables premières vp par pi et : pour chaque premier <= sqrt de n ok....
c'est simple je veux cribler la famille 13 mod30 , avec pi = 7 ; ("donc barrer les multiples de 7")
il me faut bien partir de l'index du produit = pi * vp; congru à 13 mod30 et n=900
7*7 = 49 pas bon
7*11 = 77 pas bon
7*13 = 91 pas bon
7*17 = 119 pas bon
7*19 = 133 == 13%30 ...ok calcul de l'index 133//30 = 4
je pars de 4 et je crible par pas de 7 de 4 ......> n//30 , puis je reviens dans cet indice et je crible par pas de 19 de 4 à 30..ensuite on reitère avec l'indice i+=1 relatif à Pi = a = 11
11110111111011111101111110111.n terminé pour pi = 7
je réitère avec pi = 11
11*7 = 77 pas bon
11*11= 121 pas bon
11*13 = 143 pas bon
11*17 = 187 pas bon
11*19 = 209 pas bon
11*23 = 253 == 13%30 ...ok calcul de l'index 253//30 = 8
je pars de 8 , je crible par pas de 11 de 8......> à 30.. et 8 + 23...étant .>30 donc 23 ne criblera rien...!
11110111011011111100111110111.n terminé pour pi = 11 car 23+8 >30
etc...on réitère avec l'indice i+1 relatif à a=13.....
Dernière modification par LEG (21-12-2018 08:56:23)
Hors ligne
#310 11-12-2018 18:51:13
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
re suite à une idée :
PS, j'ai remis au #post 303 ci-dessus ta version #"v6.2# que tu connais parfaitement. et à modifier , j'ai repris donc les explications par rapport à ta version ..
Dernière modification par LEG (21-12-2018 08:57:26)
Hors ligne
#311 15-12-2018 06:59:13
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonjour @Yoshi :
suite post ci-dessus 307 que j'ai modifié
Peut être plus simple et en optimisant l'algorithme :
il y a une autre méthode en optimisant l’algorithme.
Il suffit de partir de la boucle des nombres premiers > 5 de la fonction
n = int(n**0.5)
pour calculer le produit.
. EX : pour n= 9000 :
que l'on appelle par la fonction
pi[i] = primes_init
En effet, on part directement du carré de Pi = 7, on calcule le produit j de :
Puis on calcule l’index pour (pi1 ,pi2) et on crible par pas de,
pi1 et de pi2 ; de l’indexe.....> n//30 ; [puis on change d'indice i donc aux Pi suivants pour ne pas les réutiliser]. Ensuite on réitère avec lindice i+=1 donc Pi suivant ...
Dernière modification par LEG (21-12-2018 09:01:12)
Hors ligne
#312 15-12-2018 20:04:15
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Bonsoir
@yoshi
voila une simulation que j'ai trouvée:
premiers corresponde au nombres premiers init
import os
premiers = (7,11,13,17,19,23,29,31,37,41,43,47,53,59,61)
myArray = (7,11,13,17,19,23,29,31)
for j in (premiers):
fam = 1
for i in (myArray):
produit = j*i
if produit %30 == fam:
produit //= 30
print ("i: ", j)
print ("produit%30: ", produit)
os.system("pause")
il ne reste plus qu'à utiliser l'index pour cribler , résultat des index : , i = premiers int Eratosrhène(n)
i: 7
produit%30: 3 # index
i: 11
produit%30: 4
i: 13
produit%30: 3
i: 17
produit%30: 13
i: 19
produit%30: 12
i: 23
produit%30: 13
i: 29
produit%30: 28
i: 31
produit%30: 32
i: 37
produit%30: 16
i: 41
produit%30: 15
i: 43
produit%30: 10
i: 47
produit%30: 36
i: 53
produit%30: 30
i: 59
produit%30: 57
i: 61
produit%30: 63
>>>
Hors ligne
#313 15-12-2018 21:09:14
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : crible en python
Salut,
La semaine prochaine, j'aurai du temps.
D(un seul coup, ça a fait tilt : avec ta double boucle tu multiplies, chaque élément de premiers par chaque élément de myArray...
En math, ce type de produit est connu sous le nom de produit cartésien de deux ensembles, c'est faisable en Python.
Tu écris :
premiers = (7,11,13,17,19,23,29,31,37,41,43,47,53,59,61)
myArray = (7,11,13,17,19,23,29,31)
print(list(product(premiers, myArray))
qui donne
[(7, 7), (7, 11), (7, 13), (7, 17), (7, 19), (7, 23), (7, 29), (7, 31), (11, 7), (11, 11), (11, 13), (11, 17), (11, 19), (11, 23), (11, 29), (11, 31), (13, 7), (13, 11), (13, 13), (13, 17), (13, 19), (13, 23), (13, 29), (13, 31), (17, 7), (17, 11), (17, 13), (17, 17), (17, 19), (17, 23), (17, 29), (17, 31), (19, 7), (19, 11), (19, 13), (19, 17), (19, 19), (19, 23), (19, 29), (19, 31), (23, 7), (23, 11), (23, 13), (23, 17), (23, 19), (23, 23), (23, 29), (23, 31), (29, 7), (29, 11), (29, 13), (29, 17), (29, 19), (29, 23), (29, 29), (29, 31), (31, 7), (31, 11), (31, 13), (31, 17), (31, 19), (31, 23), (31, 29), (31, 31), (37, 7), (37, 11), (37, 13), (37, 17), (37, 19), (37, 23), (37, 29), (37, 31), (41, 7), (41, 11), (41, 13), (41, 17), (41, 19), (41, 23), (41, 29), (41, 31), (43, 7), (43, 11), (43, 13), (43, 17), (43, 19), (43, 23), (43, 29), (43, 31), (47, 7), (47, 11), (47, 13), (47, 17), (47, 19), (47, 23), (47, 29), (47, 31), (53, 7), (53, 11), (53, 13), (53, 17), (53, 19), (53, 23), (53, 29), (53, 31), (59, 7), (59, 11), (59, 13), (59, 17), (59, 19), (59, 23), (59, 29), (59, 31), (61, 7), (61, 11), (61, 13), (61, 17), (61, 19), (61, 23), (61, 29), (61, 31)]
ou
premiers = (7,11,13,17,19,23,29,31,37,41,43,47,53,59,61)
myArray = (7,11,13,17,19,23,29,31)
print([a*b for a,b in list(product(premiers,myArray))])
qui donne directement les produits :
[49, 77, 91, 119, 133, 161, 203, 217, 77, 121, 143, 187, 209, 253, 319, 341, 91, 143, 169, 221, 247, 299, 377, 403, 119, 187, 221, 289, 323, 391, 493, 527, 133, 209, 247, 323, 361, 437, 551, 589, 161, 253, 299, 391, 437, 529, 667, 713, 203, 319, 377, 493, 551, 667, 841, 899, 217, 341, 403, 527, 589, 713, 899, 961, 259, 407, 481, 629, 703, 851, 1073, 1147, 287, 451, 533, 697, 779, 943, 1189, 1271, 301, 473, 559, 731, 817, 989, 1247, 1333, 329, 517, 611, 799, 893, 1081, 1363, 1457, 371, 583, 689, 901, 1007, 1219, 1537, 1643, 413, 649, 767, 1003, 1121, 1357, 1711, 1829, 427, 671, 793, 1037, 1159, 1403, 1769, 1891]
Ça s'améliore encore pour s'adapter à ce que tu veux, mais ce qui précède est du vite fait sur le gaz...
Vu que c'est une fonction built-in, elle est plus rapide et plus économe que la même chose refaite par nous...
Je te laisse méditer.
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#314 15-12-2018 23:54:49
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Voila , impeccable . mais il faut l'adapter au criblage, on va remplacer le mot myArray par Pi si besoin.
Et il va falloir cribler par pas de pi et de premier en partant de l'index.....
rentrer ta fonction avec (from prodduct...etc),
puis calculer l'index du produit A*B de ta fonction ....en espérant que de l'index on puisse partir cribler directement avec A, puis B
sinon: obligé de recalculer B*A index et criblage avec B ....
c'est cette idée qui fonctionnerait en principe le mieux ; si on peut paramétrer directement l'index des 2 pi = a*b ou d'un seul si a², du produit j en utilisant ton idée des Pfam comme dans Goldbach afin d'aller cribler pour chaque indice i traité... ...qu'en penses tu...
@+
Gilbert.
Dernière modification par LEG (21-12-2018 09:05:51)
Hors ligne
#315 17-12-2018 13:31:10
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
re
voila ce que j'ai fais :
mais il y a erreur sur le résultat > 900 à cause de la sqrt n j'ai remis sqrt 2n ..???
from time import time
from os import system
from collections import OrderedDict
## V. 6.2 ##
def eratostene(n):
n = int((2*n)**0.5)
m = (n-1) // 2
limite=1+n
b = [True]*m
premiers = [2]
for i,p in enumerate(range(3,limite,2)):
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
debut,pas=j,2*i+3
for j in range(debut,m,pas):
b[j] = False
debut=i
for i in range(debut,m):
if b[i]:
premiers.append(p)
p += 2
#print(premiers)
return premiers[3:]
def CribleG3Y_mod30(n):
# INITIALISATION
global nombres,nbcell
start_i= time()
Primes_init = eratostene(n)
nbcell = n//30
nombres = []
for i in range(1):
nombres.append([1]*nbcell)
P8 = {7:0} #pour 8 fam remettre les 8[1,7,...,29]
s_1=time()-start_i
print("Phase d'initialisation: %s seconds ---" % s_1)
# FAMILLES POUR CHAQUE Pi
start_time = time()
for i,pi in enumerate(Primes_init):
for b in (Primes_init)[i:]:
j = pi*b
Fam = [0] #pour 8 fam remettre les 8[0,0,...,0]
if j%30 == 7: # changer le paramètre pour une fam fxée
fam = P8[7] # changer le paramètre pour une fam fxée , pour P8fam remettre [j%30]
if not Fam[fam]:
Fam[fam] = 7
debut_index = j//30
Nombres_fam = nombres[fam]
for index in range(debut_index, nbcell,pi):
Nombres_fam[index] = 0
s_23=time()-start_time
print("Bloc S2_s3 : %s seconds ---" % s_23)
#print(Nombres_fam)
# CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
start_time = time()
total = 0
for sous_liste in nombres:
total += sum(sous_liste)
s_4=time() - start_time
s=s_1+s_23+s_4
print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
return total,s
n = int(input("Donnez la valeur de n = 30k : "))
nbr,s = CribleG3Y_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")
résultat :
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 300
crible:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
Nombre premiers criblés famille 1: 8 ----- 0.0
--- Temps total: 0.01 sec ---
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 600
crible:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1]
Nombre premiers criblés famille 1: 12 ----- 0.0
--- Temps total: 0.01 sec ---
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 900
crible:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0]
Nombre premiers criblés famille 1: 18 ----- 0.01
--- Temps total: 0.01 sec ---
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 30000
Nombre premiers criblés famille 1: 465 ----- 0.0 ..FAUX
--- Temps total: 0.01 sec ---
Ensuite si je change le paramètre de la fam et que je met 7 au lieu de 1
à la ligne GCrible
GCrible(premiers, n, 1)
Dernière modification par LEG (21-12-2018 09:08:04)
Hors ligne
#316 17-12-2018 14:32:18
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : crible en python
Re,
Ça, c'est une horreur :
crible[index] = 0
Je me demande pourquoi Python ne râle pas et comment il fait pour ne pas se paumer...
J'ai remplacé, parce qu'à mes yeux plus rationnel, par :
crible[idx] = 0
Sauf s'il y a une raison profonde : index à la fois indice de boucle et indice de départ de boucle ???
Là, tu m'en bouches un coin :
1. Qu'est-ce que ce f fiche là ? print(f...
Je l'ai viré erreur de syntaxe. Une résurgence de printf( ?
2. Ou alors ce f a une raison d'être que j'ignore parce que, après ces modifs, je tombe sur ça :
Donnez N: 30000
Nombre premiers criblés famille {fam}: {total} ----- {int((time()-start_crible)*100)/100}
--- Temps total: {int(temps*100)/100} sec ---
Quel est le rôle de ces accolades entre guillemets ? "... {fam}... {total}..."
Elles devraient afficher les valeurs de fam, total, etc... et il n'en est rien...
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#317 17-12-2018 15:26:44
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
RE :
tu as raison pour ça:
crible[idx] = 0
pour le: print(f"Nombre premiers criblés famille {fam}: {total} ----- {int((time()-start_crible)*100)/100}")f
il m'avait dit que c'était pour calculer le temps des différentes fonctions le total....
Mais en plus chi... alors que c'était plus simple su tes programmes...!
Ensuite j'ai rien compris à ses {fam}: {total} que l'on peut virer....
En définitive pour imprimer il fait print une fois en haut....? ouù ..?
et ça lui imprimait toute les fonctions
au lieu de le faire par étape...d'ailleurs je me suis em.... pour imprimer les index, les nombres ..etc , j'ai juste réussi à débloquer print Gcrible
pour éditer les [11111111111111111111]
C'est pour cela que je pense qu'il vaut mieux modifier à partir de ta version #v6. 2# c'est à dire cribleG3Y... mais je pense que l'on a pas besoin des pfam...de toutes les façons cela ne gène en rien pour la limite et rapidité car le GCrible ne va pas plus vite....alors qu'il n'utilise pas les pfam...
Dernière modification par LEG (17-12-2018 15:40:03)
Hors ligne
#318 17-12-2018 16:23:29
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : crible en python
Salut,
Bon, je vais chercher à comprendre quand même...
Déjà, là :
def main():
# On demande N a l'utilisateur
n = demander_N()
# On récupère les premiers entre 7 et √2N
premiers = eratostene(n)
#lprint("premiers:", premiers)
#print(f"nombres premiers entre 7 et {int((2*n)**0.5)}: {len(premiers)}")
start_time = time()
# On crible
GCrible(premiers, n, 7)
temps = time()-start_time
print("--- Temps total:", int(temps*100)/100,"sec ---")
Plus l'index changé en idx, plus de message d'erreur pour 7 :
Donnez N: 30000
Nombre premiers criblés famille 7 : 459 ----- 0.0
--- Temps total: 0.03 sec ---
@+
[EDIT]
Quelle version de Python as-tu pour que le print (f... marche chez toi ? >=6 ? et ton petit-fils ?
J'ai vu passer que depuis Python 3.6, l'affichage peut sez gérer avec des f-strings : je vais aller regarder ça de près : je suis toujours en 3.5 : ceci expliquerait peut-être cela ?
[EDIT2] Bingo... Voilà ce que dit la doc officielle :
event = 'Referendum'
print(f'Results of the {year} {event}')
'Results of the 2016 Referendum'
Dernière modification par yoshi (17-12-2018 17:27:16)
Arx Tarpeia Capitoli proxima...
Hors ligne
#319 17-12-2018 16:42:07
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Ca prend tournure...
Pour n = 30000
fam =7
total nombre premiers avec l'exécutable nbpremier win32:
Allocation du Tableau en cours...
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
29947
>trouvé à la position:
407
au lieu de
459
en 0,03..secondes , comme pour la fam 1 ??? problème .
nombre de premiers pour n = 30 000, par fam {1,7,11,.....29}
{403-1 ; 407; 406; 406; 411; 395; 408 et 407 }
Dernière modification par LEG (17-12-2018 16:47:25)
Hors ligne
#320 17-12-2018 16:45:31
#321 17-12-2018 16:49:50
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
moui mais pour moi c'est ..... ????
ma version, c'est 3.7.64 bit de juin 2018
mon petit fils aucune idée, mais je pense que c'est 3.5 c'est ce que j'avais en décembre 2017...
voila ma version:
Python 3.7.1rc1 (v3.7.1rc1:2064bcf6ce, Sep 26 2018, 15:15:36) [MSC v.1914 64 bit (AMD64)] on win32
pour te donner un ordre d'idée le nombre de premiers de 7 à n par la fonction :
$ \frac {(n/2)} {Ln(n/2)} + \frac {(n/2)} {Ln(n)}$ = 392 ; pour n = 3000 toujours < à $\pi(n) = 407$ fam.7
pour n = 3 000 000 000 ; fam 1
nbpremier donne :
>Le dernier nombre est:
2999999341
>trouvé à la position:
18 054 607
Gcrible donne : Nombre premiers criblés famille 1: 19 997 341 ----- 15.0
--- Temps total: 15.19 sec ---
si c'était du blé..il vaut mieux GCrible....LoLLL
Dernière modification par LEG (17-12-2018 17:16:42)
Hors ligne
#322 17-12-2018 17:48:44
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
re :
Je pense peut être, qu'il saute des nombres premiers pi qui criblent et de ce fait cela augmente le nombre d'entier [1] qui ne sont pas marqué[0]
à cause de l'index qui serait mal mis...mais pourquoi dans ce cas, jusqu'à 600 le marquage des [1] en [0] est bon....???
Hors ligne
#323 17-12-2018 19:36:32
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
RE :
voici des exemple pour fam :1,7,11
== RESTART: E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py ==
Donnez N: 300
crible:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
Nombre premiers criblés famille 1: 8 ----- 0.0
--- Temps total: 0.01 sec ---
>>>
== RESTART: E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py ==
Donnez N: 300
Traceback (most recent call last):
File "E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py", line 81, in <module>
main()
File "E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py", line 76, in main
GCrible(premiers, n, 7)
File "E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py", line 57, in GCrible
for idx in range(index, lencrible, a):
UnboundLocalError: local variable 'index' referenced before assignment
>>>
== RESTART: E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py ==
Donnez N: 300
Traceback (most recent call last):
File "E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py", line 81, in <module>
main()
File "E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py", line 76, in main
GCrible(premiers, n, 11)
File "E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py", line 57, in GCrible
for idx in range(index, lencrible, a):
UnboundLocalError: local variable 'index' referenced before assignment
>>>
je prend n= 600; fam = 1
Donnez N: 600
crible:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1]
Nombre premiers criblés famille 1: 12 ----- 0.0
Donnez N: 1200
crible:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1]
Nombre premiers criblés famille 1: 22 ----- 0.01
Donnez N: 1800 : 121 est devenu premier...?
crible:[1, 1, 1,0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1], 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0]
pour n =2100 et fam = 1
Donnez N: 2100 ; 91 et 121 = 0,0 sont = 1,1..?
crible:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0]
Nombre premiers criblés famille 1: 38 ----- 0.01
que veut dire : lencrible = len(crible) et ensuite il s'en sert dans cette fonction :
crible[idx] = 0
on appelle à cribler ..? pourquoi ne pas avoir mis aussi lencrible[idx] = 0 ???
Hors ligne
#324 17-12-2018 19:54:31
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : crible en python
Salut,
Je trouve ce morceau curieux :
for a in (premiers):
for b in (premiers):
j = a * b
if j%30 == fam:
index = j // 30
# On crible directement avec l'index
for idx in range(index, lencrible, a):
crible[idx] = 0
Pourquoi donc ?
Pour un a donné, on passe en revue tous les j=a*b et pour chaque b on teste si a*b%30==fam
Si oui, on passe index à j//30... et on continue les b jusqu'au prochain index.
Donc, au minimum pour tous les b, on a donc donc 1 valeurs de index, stockées nulle part ou traitées à la volée nulle part.
Ce n'est que lorsque pour un a donné, on a passé en revue tous les b possibles donc qu'on sort de la boucle for b qu'on crible avec l'index... Mais lequel ?
Avec cette indentation seulement le dernier calculé....
Après vérification pour n =3000
premiers=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
Nombre d'index correspondant pour chaque a :
1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 1
D'autre part, si on a déjà testé le produit 7 * 13 (par exemple) pourquoi tester le produit 13*8 ? la réponse sera la même...
perte de temps !
On peut ainsi pour n =3000 passer à 91 tests au lieu de 169...
J'écrirais donc :
for b in premiers[i:]:
j = a * b
if j%30 == fam:
index = j // 30
@+
[EDIT]
local variable 'index' referenced before assignment
veut simplement dire que lorsque tu fais for idx in range(index...
ta ligne ne sait pas ce que c'est que index, ni ce qu'il vaut : before assignment = avant qu'une valeur lui ait été assignée (donnée)...
Dernière modification par yoshi (17-12-2018 19:58:17)
Arx Tarpeia Capitoli proxima...
Hors ligne
#325 17-12-2018 20:49:50
- LEG
- Membre
- Inscription : 19-09-2012
- Messages : 694
Re : crible en python
Tu as entièrement raison à ce sujet...moi j'ai juste essayé de trouver pour calculer l'index si le produit j%30 == fam
mais je ne sais pas comment positionner les lignes...!
Je vais copier et coller tes lignes...et tester.
Car effectivement je regarder et j'ai bien vu que le produit et son debut index n'était pas marquer [0] par exemple avec fam = 7 et n=4500
j = 7*31 = 217
217//30 = 7
et bien la 8eme cellule indice 7 était marquée [1], idem pour la cellule index 22 relatif à 23*29...
@+
RE ça n'a rien changé toujours les erreurs fam 1 et 7
== RESTART: E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py == 91 , 121 , = 0,0
Donnez N: 4500
crible:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0]
Nombre premiers criblés famille 1: 79 ----- 0.0
--- Temps total: 0.01 sec ---
>>>
== RESTART: E:\Documents\Conjecture de Goldbach\Crible_Eratosthène_Mod30.py == 187 , 217 = 0,0, 247 ok = 0
Donnez N: 4500
crible:[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0]
Nombre premiers criblés famille 7: 84 ----- 0.01
--- Temps total: 0.01 sec ---
>>>
Dernière modification par LEG (17-12-2018 20:59:26)
Hors ligne