Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 21-09-2021 06:52:00

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

Modifier un programme C++

Bonjour
Si quelqu'un pouvait si possible, m'aider à modifier ce programme C++ ; ci joint avec les explications de l'algorithme P modulo 30 dans le document joint.
Tel qu'il a été programmé à l'époque en 2003, par un étudiant à l'ESSI de Sophia Antipolis Alpes Maritimeil;  il y a deux anomalies

la première :) lorsque la "Tbase" appartenant à [7 ; 31] extrait son conjoint , elle doit avant de lancer son conjoint P uniquement que si et seulement si il est < à racine de N , la limite du crible, ce qui n'est pas le cas, d'où des milliers de conjoints > racine de N criblent inutilement...etc

Je pense que c'est dans cette partie du programme


void Algo::makeTab(){
  int cptBase ;
  int pourcent =0;
  long nbpourcent =0;
  long nbdix = nbCase/10 ;
  std::cout << pourcent << "% effectue..." << std::endl ;
  while(nbBase>0){
    for (cptBase=0 ; cptBase<nbBase ; cptBase++){
      if (tBool[tBase[cptBase].ind]==0) {
  tBool.set(tBase[cptBase].ind);
  if (tBase[cptBase].bnb%tBase[cptBase].nb!=0)  // si le conjoint bnb est < racine carrée de la limite N
    getOut(cptBase);
      }
      tBase[cptBase].next();
      if (tBase[cptBase].ind>nbCase)
  tBase[cptBase].stop=1 ;

    }
    if (tBase[0].ind>nbpourcent+nbdix){
      nbpourcent=tBase[0].ind ;
      pourcent+=10 ;
      std::cout << pourcent << "% effectue..." << std::endl ;
    }
    MAJtBase();
  }
}

void Algo::MAJtBase(){
  int i;
  for (i=0 ; i<nbBase ; i++){
    if (tBase[i].stop==1){
      int j;
      for (j=i ; j<nbBase-1 ; j++){
  tBase[j].bnb=tBase[j+1].bnb;
  tBase[j].nb=tBase[j+1].nb;
  tBase[j].ind=tBase[j+1].ind ;
  tBase[j].stop=tBase[j+1].stop ;
      }
      nbBase--;
    }
  }
}
 

Puis deuxième modification :

remplacer les Tbases [7 ; 31] par les new Tbase > 31 appartenant à {37,41,43,47,79,53,59,61}  79 remplace 49 qui n'est pas premier
mais pas avant d(avoir lancer les 8 bases [7;31]cribler leurs multiples jusqu'à la limite N puis sorte de l'algorithme break retour à l'Algo avec les New Tbase
exemple avec la série 13  :


void Algo::makeTab13(){
  theSerie = 13;   // lancer en debut d'Algo les 8 bases de 7 a 31 a partir de leur cellule set( ),jusqu'au bout et marquent leur mulitples
  tBool.set(0);     // puis retour au programme avec les nouvelles Tbase de 37 a 79 dans leur cellule set()et on lance l'Algo
  tBool.set(4);  // (7.19) ... set(97)(37,79)
  tBool.set(8);  // (11.23)... set(72)(41,53)
  tBool.set(13);  // (13.31) ... set(87)(43,61)
  tBool.set(16);  // (17.29)... set(92)(47,59)
  tBase = new Base [8];
  nbBase = 8;
  tBase[0] = Base (7,79,18);   // (37,109,134)
  tBase[1] = Base (19,37,23);  // (79,67,176)
  tBase[2] = Base (11,53,19);  // (41,83,113)
  tBase[3] = Base (23,41,31);  // (53,71,125)
  tBase[4] = Base (13,61,26);  // (43,151,216) // ici bnb 91 et 121 non prime donc tBase 43 et bnb 151 cellule 216
  tBase[5] = Base (31,43,44);  // (61,73,148)
  tBase[6] = Base (17,59,33);  // (47,89,139)
  tBase[7] = Base (29,47,45);  // (59,107,210) // idem 77 non prime donc tBase 59 et bnb 107 cellule 210
  makeTab();
}
 

Voici le programme complet dans sa forme basic , qui est en fin de document avec les explications du déroulement de l'algorithme en début de document avec somme exemple le tableau série 23%30 et série 1%30.
Programme que je met dans le sujet réponse suivant pour ne pas surcharger...
Merci d'avance ...[le but étant de comparer la densité de premiers jumeaux par famille avec la densité de premiers ayant un écart de 246 suite au projet Polymatrh, ayant démontrer qu'il y aurait une infinité de nombres premiers $p +246 = q$ .

Or si cette densité est équivalente lorsque N tend vers l'infini, car c'est une conséquence du fonctionnement de l'algorithme avec ses 8 bases qui tournent en boucle, afin d'extraire leur conjoint (bnb +30) quelque soit une des 8 familles $(i)\in{(1,7,11,13,17,19,23,29)}$. Alors il est clair qu'il y a une infinité de premiers jumeaux Pj, $p + 2 = q$ conséquence de la démonstration du projet Polymath pour $p+246=q$

Je viens de tester ce programme en ayant modifier le départ des bases de [7 à 31] par celle de [37 à 79] on ne gagnerai que 3 minutes alors que le programme Ératosthène.Cpp, ci dessous il va 11 fois plus vite....

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

Dernière modification par LEG (21-09-2021 13:52:32)

Hors ligne

#2 21-09-2021 07:01:25

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

Re : Modifier un programme C++

Re suite du post ci-dessus avec le programme complet de l'algorithme.

Par série, la position des Tbase dans leur cellule est indiqué par l'index set() qui est égal au produit du couple de Premiers ((p'*q)- i )/30 = set(..) avec (i) appartenant à {1,7,11,13,17,19,23,29}

Ce programme existe en Python (établi par Yoshi voir sous forum programme en python...), mais modifié, seule problème il ne sauvegarde pas les nombres premier trouvés par fichier....
peut être faudrait il juste ajouter cette fonction en fin de programme....si possible....

Je met le programme transformé en C++, Car je pense qu'il serait plus simple de modifier celui ci, en rajoutant la fonction qui sauvegarde les 200 derniers , en partant de la fin du tableau si possible ou lors de la fonction :

cout << "Nombre premiers criblés famille " << fam << " plus petits que "<< n <<": " << total;// << " time " << (clock()-cl)*1e-6<< endl;
  return total;

Ou encore une fonction qui imprime le tableau criblé inférieur à 300 lignes c'est à dire le tableau de 1 .0.1.1.0.0 0 ...etc


// -*- 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 ECrible(const vector<ulonglong> &premiers, ulonglong n, int fam, vector<bool> &crible, size_t lencrible){
  int cl=clock();
  size_t 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/1500000,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> temp;
  ulonglong debut = 1200000000;
  ulonglong fin = 1200000015;

 vector<int> familles;
  familles.push_back(1);
  familles.push_back(7);
  familles.push_back(11);
  familles.push_back(13);
  familles.push_back(17);
  familles.push_back(19);
  //familles.push_back(23);
  familles.push_back(29);

  for (int i = 0; i < familles.size(); i++)
  {
    int fam = familles[i];

    for (ulonglong limite = debut; limite < fin; limite += 15)
    {
      cout << "famille : " << fam << " limite : " << limite << endl;
      double sqrtN = unsigned(std::sqrt(double(limite)));
      fill_crible(temp, sqrtN);
      vector<ulonglong> premiers;
      for (ulonglong p = 7; p <= sqrtN;)
      {
        premiers.push_back(p);
        p = nextprime(temp, p);
        if (p == unsigned(-1))
          break;
      }

      size_t lencrible = limite/30;
      vector<bool> crible(lencrible, true);
      ECrible(premiers, limite, fam, crible, lencrible);
    }
  }
}

 

Dernière modification par LEG (01-12-2021 09:30:03)

Hors ligne

#3 22-09-2021 08:28:25

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

Re : Modifier un programme C++

Bonjour LEG,

Qu'est-ce-que tu entends par "qui sauvegarde les derniers nombres premiers dans un fichier de 15 000 000 de nombres , en partant de la fin du tableau si possible" ?...
Tout est toujours possible, mais cela oblige à conserver les 15 000 000 de nombres premiers jusqu'à la fin, au lieu de les enregistrer au fur et à mesure...
Je vais voir ce que je peux faire.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#4 22-09-2021 09:30:16

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

Re : Modifier un programme C++

Bonjour Yoshi

Merci de ta réponse:

Sauvegarder les derniers nombres premiers trouvés, environ 15 000 000 pour un seul fichiers

Par exemple il me faut les nombres premiers > 30 000 000 000, je lance l'algorithme  "Programme" je rentre la limite demandée par exemple 60 000 000 000 et deux familles ou une....
et je sauvegarde les 15 000 000 derniers , autrement dit il faut que le programme à la demande, sauvegarde dans un fichier les derniers nombres premiers trouvés en commençant par la fin...

Sinon cela fait trop de fichiers, et si ils sont trop volumineux c'est galère pour les ouvrir je pense même que 10 000 000 pour un fichier c'est suffisant.

le programme C++ qui est joint et très rapide environ 2 minutes pour une Famille et la limite N = 1200 000 000 000
c'est pour comparer la densité de premiers ayant 2 d'écart et 246 d'écart par tranche de 100 nombres...

Je compare donc deux fichiers, les familles jumelles 11 et 13 modulo 30 pour les Pj, puis les deux familles 11 et 17 modulo 30 pour les P + 246 = q .

je pensai qu'une fois le programme terminé , il fait la somme des 1 = premiers qu'il a donc en mémoire , puis il faut rétablir leur valeur par exemple
Famille 30k +11 uniquement pour les [1] , [0] puis à la fin il sauvegarde les derniers....

Donnez N: 60000
crible: [1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0,
..........(11,41,71,101,131,..191...221,251,281,.....,371.....etc
Mais si tu penses qu'il faut les sauvegarder au fur et à mesure dans la mémoire virtuelle , et puis sauvegarder les derniers dans un fichier ...

Il me faudrait les 200 derniers nombres premiers ça me conviendrait bien....

@+

Dernière modification par LEG (01-12-2021 09:31:11)

Hors ligne

Réponse rapide

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

E-mail (obligatoire)

Message (obligatoire)

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

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante dix moins soixante trois
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums