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

Répondre

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)?
deux plus cinquante 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.

Retour

Résumé de la discussion (messages les plus récents en premier)

LEG
14-01-2019 14:14:22

Bonjour @Yoshi

je met ci dessous le crible Ecrible Ératosthène en C++, que Mr B Parisse à eut la gentillesse de transformé , sur la base de ton programme Python.
il faut faire attention au ['i] où il faut enlever l'apostrophe ' que j'ai dû mettre pour pouvoir l'éditer.


// -*- compile-command: "/usr/bin/g++ -g goldbache.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 produit;
    int GM[]={7,11,13,17,19,23,29,31};
    for (size_t j=0;j<sizeof(GM)/sizeof(int);j++){
      produit = p*GM[j];
      if (produit %30==fam){
  produit /= 30;
  break;
      }
    }
    indices[i]=produit;
  }
  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 << " plus petits que "<< n <<": " << 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 sqrtN=unsigned(std::sqrt(double(N)));
  fill_crible(crible,sqrtN);
  vector<ulonglong> premiers;
  for (ulonglong p=7;p<=sqrtN;){
    premiers.push_back(p);
    p=nextprime(crible,p);
    if (p==unsigned(-1))
      break;
  }
  GCrible(premiers,N,fam);
  cin>>N;
}
 

Ce qui permet d'avoir les deux cribles E et G, en C++, par famille arithmétique de raison 30
@+
Leg

LEG
02-01-2019 09:04:19

Bonjour à tous
j'espère que 2019 verra tous vos projets se concrétiser, et qu'elle vous apporte le meilleur de cette nouvelle année...
@Yoshi je te remercie pour toute l'aide que tu m'as apporté en 2018, en espérant que 2019 te le rende passe une très très belle année.
A +
Gilbert.

Le crible converti en C++ a une limite de 7500 000 000 000 , et pour Goldbach de N à 2N = 15 000 000 000 000 .
je pense que même en améliorant Ce crible Ératosthène , comme indiqué ci dessus  pour l'optimiser, change de beaucoup sa limite et vitesse.. Mais c'est comme cela qu'il devrait fonctionner, en incrémentant de 30 les Ai> 31.

pour info:
Crible É
Pour n = 6000 mds, nombre de premiers  13 mod 30, 26 422 717 616 en 1 677,97 secondes
Pour n =7500 mds, nombre de premiers 13 mod 30, 32 770 358 492 en 2142,95 secondes

Grible G, pour fam = 13
Pour n = 6000 mds , nombre de premiers  17 mod 30, entre 6000 et 12 000 mds = 25 161 218 215  en 1 625,3 secondes
Pour n = 7500 mds , nombre de premiers  17 mod 30, entre 7500 et 15 000 mds = 31 217 840 128  en 2181,1 secondes

LEG
26-12-2018 07:24:36

Donc tu penses que même en incrémentant Ai de 30 , pour calculer l'index suivant...de la liste des Ai, ça ne ferait pas tellement gagner de temps ("il faut quand même vérifier que Ai+30 est bien dans la liste Ex 13*19; puis 13 * (19+30) faux out, donc 13*(49+30) > 73 donc out..on passe à Bi suivant =17...
Pourtant lorsque l'on incrémente Ai de 30, on incrémente par la même son idx de Bi appartenant au GM:
EXemple fam = 7: B1 = 11 ; Ai = 17 , idx = 6 ; on aura donc Ai +30 = 47 , donnera idx + 11 =17

Tu as peut être raison, car les deux algorithmes curieusement sont aussi rapides l'un que l'autre...et traduit en C++ , même temps d'exécution pour une même limite N = 128 700 000 000; en 13 secondes...!
l'un calcule des restes que l'on incrémente de 2*pi jusqu'au %30==fam, pour ensuite calculer l'idx....et l'autre calcule les produits (b*a) ....>%30 == fam ; puis idx..., et :

1)_ Criblage de l'idx par de pas $p_i\leqslant\sqrt{2n}$ , pour Goldbach .
2)_Criblage de l'idx par de pas $A_i\leqslant\sqrt{n}$ , pour Ératosthène .

Alors que G, crible avec plus de premiers que É ....? De plus, G crible de l'idx plus petit que celui de E..d'où plus de cellules à marquer...? Comme quoi cela n'influence pas beaucoup le temps d'exécution...Que ce soit en python ou en C++ .

Par contre en C++ par rapport à python il n'y a pas photo....en terme de rapidité * 500 et de limite * 4 ...! Et encore j'utilise Code:bloc qui est en 32 bits sous Windows et non en 64.... ils l'on testé en 64 bits il a mis un peu moins de 60 secondes pour n = 450 000 000 000 ce qui donne pour G de 450 GO à 900 Go...!

Un petit résultat :

Avec Goldbach ; fam 7: nombre de nombres premiers entre 510 000 000 000 et 1020 000 000 000 =
2 331 532 960 en : 55,111 secondes

Avec Ératosthène ; fam 7: nombre de nombres premiers de 7 à : 510 000 000 000 =
2 459 907 472  en : 55,158 secondes

Je les ai testé jusqu'à 1200 GO en 75 secondes chacun à 2 secondes près..

Record ou Pas : sur le site Bibm@th du plus grand nombre de nombres Premiers criblés élémentairement, entre N et 2N ..?

RÉSULTAT Pour N = 3 billions , fam = 11: par Gcrible_mod 30
  nombre de premiers criblée de 3 billions à 6 billions = 12 880 098 499 en  734,93 secondes

Par E_crible_mod30 :
Pour N = 3 billions, nombre de premiers  11 mod 30, de 7 à N : 13 542 540 483 en 735,5 secondes

Voila un bon crible de noël , Mr ..YOSHI..
@+ LEG

yoshi
25-12-2018 09:17:48

Re,

Noyeux Joël à toi aussi...
Je ne m'attendais pas à une réponse un 25 déc.
A) Ton objection est à examiner de près...

B) Je pensais bien que ce serait coton... Je n'espérais pas une solution obtenue d'un simple claquement de doigt.  Je suis têtu, un peu Saint Thomas et probablement un lointain descendant de Guillaume d'Orange :
Il n'est pas  nécessaire d'espérer pour entreprendre ni de réussir pour persévérer...

Sinon, j'ai une 2e idée en réserve, un peu plus ch... ou moins, c'est selon, mais probablement plus lente.
* Considérer une liste de 1000 nb 1
* Ecrire à la place un nb binaire de 1000 bits égaux à 1 (ce qui correspond au décimal $2^{125}-1$)
* transformer le bit n° idx (compté à partir de la gauche) en un 0
* Lorsque c'est fini, compter le nb de 1

2e variante (douteuse) :
....
* transformer le bit idx (en partant de la droite et en progressant de D à G cette fois) en un 0
* transformer le nombre binaire restant une fois fin en décimal

Mais tester ce genre de choses demande de disposer d'un petit confoert de programmation, ce que je n'ai pas ici...

@+

LEG
25-12-2018 09:09:06

re :
POUR N = 6000, c'est faisable en 46 opérations , tu peux regarder , je disais que cela allez plus vite, car pour les 8 nombres premiers A, de la liste A, des-que A%30== 7 ,l'index est calculé, A = 31 crible;
Pour le calcule de l'index suivant, on incrémente Aide  30 qui serra obligatoirement =7%30 , et donc  re calcule de l'index..de Ai = 61..qui crible, puis Ai+30 = 61 > 73 la boucle B = 7 est fini. i += 1 , B =11

B = 11; "", 11*17 ok idx = 6, 17 crible, suivant : 11* (17+30) idx = 6+11, crible, .suivant 11*(47+30) si par exemple 77 qui n'est pas dans la liste A car il n'est pas premier; pas de problème, on incrémente de 30 Ai et suivant : 77+30 = 107 >73...fin de boucle B pour i = 1, B = 11...!

("C'est à peu près le principe de l'algorithme nbpremier c++ de 2003 , car cette optimisation est justement meilleur que nbpremier")

En inversant les deux listes du programme; les 8 boucles B du GM vont parcourir la liste A des nombres premiers d'Eratosthène                         

B = [7, 11, 13, 17, 19, 23, 29, 31]   n= 6000   Fam =7    nbcell = 6000/30 = 200 à cribler
--------------------------------------------------------------------------------------------
A = 7,,,,11,,,,13,,,,17,,,,19,,,,23,,,,29,,,,31],,,37,,,41,,,43,,,47,,,53,,,59,,,61,,,67,,71,,73]
-----------------------------------------------------------------------------------------------
7 """"  """"  """"  """"  """"  """"  """"  217].,......  ,...... ,...... ,...... ,...... ,......,427..,......  ,...... ,......,
11  """"  """"  """"  187,......,......,......,......]....., ......,......,.697.,.....,......,......,.......,......,......,.
13  """ """"  """"  """"  247..,......  ,...... ,].....,......  ,...... ,...... ,...,on saute49.. ,...... ,...... ,...... ,...... ,.....,.....,
17  """"  187 ,.....  ,...... ,...... ,...... ,...... ,]..... ,...... 697....,..... ,...... ,...... ,...... ,...... ,...... ,......  
19  """"  """"  247.. ,...... ,...... ,...... ,...... ,]..... ,...... ,...... 817...,...... ,...... ,...... ,...... ,...... ,...... ,
23  """"  """"  """"  """"  """"  """"  667.. ,]..... ,...... ,...... ,...... ,...... ,......667... ,...... ,...... ,...... ,
29  """"  """"  """"  """"  """"  667.. ,...... ,]..... ,...... ,...... ,...... ,.......667.. ,...... ,...... ,...... ,...... ,
31...217..,.....,.....,.....,.....,......,...... ,..... ,].1147.....,......,......,...... ,...... ,......,2077,.....,.....,
--------------------------------------------------------------------------------------------------------

Ce qui supprime toutes les opérations de calcule: produit et modulo pour tout Ai > 31 .
incrément = 30 : Ai + 30, +30 ...+30k  et on peut "aussi" incrémenter l'index de: Bi si c'est plus rapide...

D'où , il n'y a que les 8 boucles GM quelque soit le nombre de Ai, de la liste A .
Ainsi que les 8 opérations au maximum, des Ai <= 31, pour trouver les 8 index et ensuite : Bi * [Ai +30k]

C'est faisable...?

illustration, en partant du carré des nombres premiers Bi de la liste GM :

Exemple : on a choisie fam =1 , i = 0, Bi=7:
7*7, 7*11, (7*13) == 1%30. L’index du couple est 3 ; [7 et 13] vont cribler par pas de 7 et de 13, de 3 → n//30.

Une fois terminé on fait un break et on les incrémente de 30, pour réitérer et continuer avec Bi+30 ; (7+30 , 13 +30)qui sont bien dans la liste des Ai(premiers), (« sinon on augmente de 30 jusqu’à fin de liste des Ai(premiers) donc <= 89. »).

Ce qui donne :(Ai)² = 37*37 , calcul index et criblage, puis 43*43, index et criblage. Break ; on incrémente à nouveau ces deux Ai (37 et 73 )de 30 ; soit: 67*67, index et criblage ; puis 73*73, index , criblage ; fin pour ces deux Familles Bi[30].
On passe à Bi suivant.

Suivant Bi=11 : (11*11) == 1%30 ; index 4 et crible par pas de 11, de 4 → n/30.
Break ; on incrémente Bi de 30 ; soit Ai = 41, produit = 41*41 ; index, criblage,break et on incrémente à nouveau de 30 tant que Ai +30k est <= à  sqrt n fixé, soit 89 pour cet exemple.
Donc :71*71 , index, criblage ; fin pour cette Famille Bi[30].
On passe au suivant.
Bi suivant = 17 car la famille Bi = 13[30] a déjà été utilisé et finie….

17*17, 17*19, 17*23 == 1%30 ; calcule de l’index pour le couple (17,23)//30 = 13 le couple va cribler par pas de 17 et de 23 ; de 13 → n/30 , break, on incrémente de 30 : 17 et 23 , produit des carrés, index, criblage fin des deux Familles Bi = 17 et 23 [30]
etc ….etc.
On réitère avec Bi suivant = 19…. etc…jusqu’à la dernière Famille Bi=31[30].
A la fin on fait le total des [1] qui donnera le nombre de nombres premiers : q[n ; 2n].

le programme est un peu plus difficile, mais on supprime beaucoup d'opérations...

LEG
25-12-2018 07:34:03

Bonjour Yoshi
j'attendais le père noël après 21h30 ...pour qu'il m'apporte ses idées....je te remercie et j'espère que tu vas bien en profiter .

A_)
concernant tes 50 boucles.. ok..Mais je pensais vraiment que c'était plus rapide 8 boucles sur 50 nombres ..! car il y a justement le phénomène qu'après les 8 premiers sur les 50 nombres premiers, il y a de plus en plus d'écart entre ces premiers, de ce fait la congruence du produit %30 ==fam, est plus rapprochée , d'où moins d'opérations lorsque n tend vers l'infini...Sur excel , manuellement je vais plus vite...

B_)
Si c'était faisable, effectivement la sommation finale est automatique..
Mais justement le problème des doublons n'est pas gérable...

n=3000 ; fam = 7 , Pi =7
ok : on a les 1000 [1], j'ai l'index 7,pour Pi = 7; par pas de 7, j'enlève un 1 à chaque pas de 7 et autant de 0 à la place..Sachant que je vais partir de 7 ....>1000 = (993/7) +1, le premier 1 enlevé au départ . J'ai enlevé 141 + 1 [1] . Somme = 1000 -142. ON est d'accord..? sous total = 858.

Pi = 11 pour l'index 6 ; même opération par pas de 11 de 6 à.....> 1000 ; soit :(858 / 11) + 1. 72 [1] d'enlevés... Où sont les doublons parmi ces 72 [1]....Comment tu les vois..? ou comment le programme va le savoir. ..?

Sachant que les doublons vont se répéter en fonction du nombres de pas UNIQUES par Pi...dixit le TFA..("thèoreme fond de l'arith..")..cela revient à prévoir la factorisation unique d'une cellule[1]...Imagine les conséquences....

Il y a un polynôme avec 26 variables de degré 25 ; qui ne prends que les nombres premiers...donc qui élimines les doublons....

tu peux illustrer et faire un essais : j'ai marqué les deux index de départ, [(0)] =7 pour Pi = 7 ; "0" 6, pour Pi =11


111111"0"[(0)]111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)111111(0)1
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

1) la seule chose que l'on sait: c'est que la cellule d'index 6 partagé par 11 *17  se retrouvera dans 187 cell, donc d'index 6 + 187 cellules, avec comme factorisation (7,11 et bien sûr 31) = 5797 et (5797-7)/30 = l'index 193..!

Quel est la factorisation de la cellule X = (7,11, z) le ou les doublons...?

au pif: 9 * 7 = 63  au départ de la 8ème cellule = 71 cellules; moins la cellule 0 =7 , cela fait 70 cellules :
vérification : 70*30 + 7 = 2107 ; 2107/7 = 301; 301 / 11 = Faux...   le conjoint de 7 avec 11, c'est 11 + 30 = 41.
cellule 106 ok....(105*30 + 7) est /7/11 et 41.
41 qui a pour index 23 donné par (17*41) // 30 ...c'est ingérable , comme le polynôme schmoldu...à 26 variables...

Je vais regarder de mon côté ce que donne le nombre d'opérations pour 8 boucles et n nombres: avec 6000...

Joyeux Noël cher ami...
Gilbert
@+

yoshi
24-12-2018 20:16:20

Re,

Je ne suis pas chez moi, jusqu'au 26, mais 450 km plus loin.
Rapidement comme ça, non !
Il y a une autre idée que je voudrais tester...

Cela dit 50 boucles sur 8 nombres ou 8 boucles sur 50 nombres, ça fait toujours 400 couples de valeurs et pratiquement un couple sur 2 à éliminer (redondance).

L'idée que je voudrais tester est de ruser avec un nombre par exemple au départ de 1000 cellules pour n=30000, ne contenant que des 1.
Au lieu de gérer 1000 cases de 1, utiliser le nombre 1000, et enlever 1 à ce nombre au lieu d'écrire 1 dans la case déterminée grâce à l'index.
Il faudrait, par contre, que je sache si j'ai affaire à un "doublon" parce que dans ce cas où dans la liste j'écrirais un 0 là ou j'en ai déjà inscrit un, j''enlèverais par contre un au nombre une fois de trop...

Ça doit être faisable...
Si ça  l'est effectivement, je réduirais autant d'accès à la liste, autant d'écriture de 0 et la sommation finale : le nombre restant donnerait automatiquement le total...

@+

LEG
24-12-2018 07:50:11

Bonjour Yoshi

est ce que tu as essayé d'inverser la boucle : a,b  en b,a:


GM=[7, 11, 13, 17, 19, 23, 29, 31] # c'est aussi une liste
premiers=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] # c'est une liste
for b in premiers:
    print ("Avec a =",a,end="    ")
    for a in GM:
        print ((a,b),end=" ") # Affichage des couples (a,b)
    print()

de sorte, que c'est B = 7 , qui va parcourir les éléments de a, calculer a%30==fam, puis calculer les index, pour chaque a trouvé, a part cribler ... jusqu'à la fin , on sort de la boucle,] puis on change d'indice i+=1 , B=11...et on réitère...???

il n'y aura que 8 boucles [Bi.....> a]

LEG
23-12-2018 18:59:00

crochets, accolades,  parenthèses...et cannes à pêche ...pour moi je nage....Est-ce que tu le veux transcrit en C++, à la suite des post...?

Ce qui veut dire aussi que pour n > 10: il existe plus de premiers entre 1 et n qu'entre n et 2n.
Et la conjecture de LEG, quelle est-elle ?

la même affirmation que toi..!
En effet les deux algorithmes criblent la même limite de 7 à N : pour compter le nombre de nombres premiers de 7 à N ou de N à 2N

or, il est simple de montrer que l'algorithme d'Ératosthène comptera plus de premiers de 7 à N car il n'utilise que les nombres premiers Pn $\leqslant\sqrt{N}$ pour marquer les multiples n de P .

Alors que l'algorithme de Goldbach, pour la même limite de 7 à N comptera plus d'entiers N congru à 2N modulo P , car il utilise les nombres premiers Pn  $\leqslant\sqrt{2N}$ d'où par obligation, moins de premiers entre N et 2N....!

Ce n'est pas une conjecture, mais une évidence....tu ne crois pas....?

c'est aussi pour cela que j'en ai déduit que le nombre de nombres premiers qu'il y a entre N et 2N vaut environ $ \frac{N}{Ln (2N)}$, pour N>= 15; et non $\frac{N}{Ln (N)}$ pour Ératosthène . Cela n'engage que moi, bien entendu..

Si j'utilise le terme de crible ou algorithme de Goldbach, cela vient tout simplement que pour compter le nombre de couples (p,q) qui décompose un entier pair >= 16, en somme de deux premiers p,q on utilise le même crible en ne comptant que les nombres premiers p <=N , qui n'ont pas été marqués par ce crible...Donc :("qui peut le plus peut le moins").....sans aucune prétention, simplement un hobby...


Passe une bonne fin de soirée
@+

yoshi
23-12-2018 18:49:03

Re,

je parle des crochets [] pas des accolades {}, hein...

@+

LEG
23-12-2018 18:46:13

ok impeccable, il marche aussi avec les crochets GM= [7,11,13...31]et sans les ( )...donc je  laisse comme ça

est-ce que tu le veux transcrit en C++...? je viens juste de le recevoir de Mr Parisse Bernard....ça déménage...

Cela serait bon comme outils sur votre site...non?

yoshi
23-12-2018 18:13:05

Re,

J'ai dit : avec un tuple, ça fonctionne et j'ajoute mais ce n'est pas naturel...
As-tu essayé de supprimer les parenthèses autour de premiers et de GM ? Elles sont inutiles.

J'aurais voulu voir l'essai chez toi en déclarant GM=[7,11,13,17,19,23,29,31], parce que chez moi, aucun problème...

@+

LEG
23-12-2018 17:09:15

bin..j'ai bien fais ce que tu indiques , avec la fonction


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

dans le programme ci dessous qui marche bien ("et aussi vite que Goldbach de N à 2N "):


from itertools import product
from time import time


def eratostene(n):
    n = int(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
    return premiers[3:]


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 lprint(text="", liste=None):
    if len(liste) < 250:
        print(text + str(liste))


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


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

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

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


main()
 

résultat :
====== RESTART: E:\executable algo P(30)\E_Crible_ gty_modifié mod30.py ======
Donnez N: 300 000 000
Nombre premiers criblés famille 7 : 2031596 ----- 1.21
--- Temps total: 1.23 sec ---
>>>

et avec ton ancienne version que j'ai posté hier :
résultat :

======= RESTART: E:\executable algo P(30)\CRIBLE_Eratosthène_Mod30.py =======
Donnez la valeur de n = 30k : 300 000 000
Phase d'initialisation: 0.09360027313232422 seconds ---
Bloc S2_s3 : 1.0608017444610596 seconds ---
Extraction des premiers de 7 à n : 0.07800006866455078 seconds ---

**  2031596 nombres trouvés en 1.2324020862579346 secondes **
>>>

yoshi
23-12-2018 16:49:38

Re

Ce que j'ai compris quand même, c'est comment écrire GM pour le faire fonctionner dans la fonction...
GM = 7,11,13,17,19,23,29,31

sans accolade..et autre...car erreur list...!

Ah bon ?
Dans ce cas, sais tu à quel type se rattache ce GM ?
Non.
As-tu posé la question à Python ? Non ?
Dommage, il t'aurait répondu :

>>> type(GM)
<class 'tuple'>

La preuve :

>>> print(GM)
(7, 11, 13, 17, 19, 23, 29, 31)

Ici, ce tuple, pour un matheux, porte le nom de octuplet...

Avec accolades, ça ne peut pas marcher, ce serait un dictionnaire, et la structure d'un dictionnaire c'est {key0:valeur0, key1:valeur1....} ou un set (je regarderas ce que c'est exactement)
Tu as de la chance :

>>> F={7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}
>>> F
{37, 7, 41, 43, 11, 13, 47, 17, 19, 53, 23, 29, 31}
>>> F[0]

Traceback (most recent call last):
  File "<pyshell#18>", line 1, in <module>
    F[0]
TypeError: 'set' object does not support indexing

Ça ne marche qu'avec cette utilisation

for a in premiers :
    for b in GM:

As tu bien vu ci-dessus l'ordre entré des nombres dans F et l'ordre restitué : en cela il se comporterait comme un dictionnaire non ordonné.

Avec un tuple, pas de souci... sauf qu'il est impossible d'ajouter, modifier ou supprimer un élément d'un tuple...

Revenons un peu sur ce que tu dis : erreur list ??? En français  ? Ce n'est pas Python qui te cause,  alors., ni Pycharm... D'ailleurs je n'ai jamais rencontré cette erreur en Python
Donc avec une liste, ça plante ??! Et pourquoi donc ?
Voyons ça :

premiers=[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] # c'est une liste
GM=[7, 11, 13, 17, 19, 23, 29, 31] # c'est aussi une liste
for a in premiers:
    print ("Avec a =",a,end="    ")
    for b in GM:
        print ((a,b),end=" ") # Affichage des couples (a,b)
    print()

Sortie :

Avec a = 7    (7, 7) (7, 11) (7, 13) (7, 17) (7, 19) (7, 23) (7, 29) (7, 31)
Avec a = 11    (11, 7) (11, 11) (11, 13) (11, 17) (11, 19) (11, 23) (11, 29) (11, 31)
Avec a = 13    (13, 7) (13, 11) (13, 13) (13, 17) (13, 19) (13, 23) (13, 29) (13, 31)
Avec a = 17    (17, 7) (17, 11) (17, 13) (17, 17) (17, 19) (17, 23) (17, 29) (17, 31)
Avec a = 19    (19, 7) (19, 11) (19, 13) (19, 17) (19, 19) (19, 23) (19, 29) (19, 31)
Avec a = 23    (23, 7) (23, 11) (23, 13) (23, 17) (23, 19) (23, 23) (23, 29) (23, 31)
Avec a = 29    (29, 7) (29, 11) (29, 13) (29, 17) (29, 19) (29, 23) (29, 29) (29, 31)
Avec a = 31    (31, 7) (31, 11) (31, 13) (31, 17) (31, 19) (31, 23) (31, 29) (31, 31)
Avec a = 37    (37, 7) (37, 11) (37, 13) (37, 17) (37, 19) (37, 23) (37, 29) (37, 31)
Avec a = 41    (41, 7) (41, 11) (41, 13) (41, 17) (41, 19) (41, 23) (41, 29) (41, 31)
Avec a = 43    (43, 7) (43, 11) (43, 13) (43, 17) (43, 19) (43, 23) (43, 29) (43, 31)
Avec a = 47    (47, 7) (47, 11) (47, 13) (47, 17) (47, 19) (47, 23) (47, 29) (47, 31)
Avec a = 53    (53, 7) (53, 11) (53, 13) (53, 17) (53, 19) (53, 23) (53, 29) (53, 31)

Ça marche !

Alors qu'as-tu fait ?

@+

LEG
23-12-2018 14:25:57

Je suis bien d'accord avec toi sur le groupe multiplicatif, et GM ...
car à l'époque de nbpremier xin 32 on ne se sert que de GM qui est un groupe  multiplicatif, où en fonction de la fam choisie, on multiplie bien les 8 nombres entre-eux pour calculer l'index des couples qui vont cribler, extraire les nombres premiers > 31, qui vont cribler à leur tour...etc etc ...je ne suis pas rentrer dans les explications de ce  crible C++ ...voila...

Bien sûr que mes explications sont lourdes...donc mal comprises pour un matheux...d'où je ne sais pas comment je dois t'écrire

GM {7,11,13,17,19,23,29,31} ,
30k+p  avec p∈[1,7,11,13,17,19,23,29] et k>= 1...
    Là, avec GM, le 1 a sauté, remplacé par le 31...

Bien sûr , 31 à la place de 1..

Ce que j'ai compris quand même, c'est comment écrire GM pour le faire fonctionner dans la fonction...
GM = 7,11,13,17,19,23,29,31

sans accolade..et autre...car erreur list...!

Je viens aussi de rectifier mon erreur d'inattention, c'est bien :

for a in (premiers):
        for b in (GM):

Pied de page des forums