Nombres premiers

Télécharger le projet
Commenter

Description

Bonjour,

Tout d'abord, j'aimerais particulièrement remercier pgl10 pour son article "Nombres premiers" du 15/03/2019.
Son code est intéressant car il évite l'opération % (modulo) et limite la taille de la mémoire auxiliaire utilisée à celle nécessaire pour enregistrer la liste des nombres premiers demandés.

En l'observant de plus près, j'ai remarqué qu'il "ressemble" assez bien à la méthode Essais de division avec liste:
   Nombres premiers: essais de division avec liste
adapté, à l'aide du "cycle" t={4,2,4,2,4,6,2,6}, au non traitement des multiples de 2, 3 et 5: 
void Division(unsigned int m, unsigned int *np) { // first m primes
  unsigned int i=5, s=0, t[]={4,2,4,2,4,6,2,6};
  np[0]=1; np[1]=2; np[2]=3; np[3]=5; np[4]=7;
  for (unsigned int n=11; i <= m; n += t[s]) {
    for (unsigned int k=4; ; k++) {
      unsigned int j=np[k];
      if (n%j == 0) break;
      if (uint64_t(j)*j >= uint64_t(n)) {np[i++]=n; break;} // n is prime
    }
    if(++s >= 8) s=0;
  }
}

Afin de montrer cette similitude, je me permets d'afficher ici le code
   CodeS-SourceS-pgl10: Nombres premiers: 
// Calcul des nnp premiers nombres premiers dans np[i],i=1,nnp
// Le tableau np doit avoir nnp+1 éléments. ( nnp > 3 )
void prems(int nnp, int* np) { // 
    const int maxi = INT_MAX, ieme = 105097565;
    int m,n,s,t[]={4,2,4,2,4,6,2,6};
    int* mp;
    if(nnp<ieme) m = nnp+1;     // Le dernier np[i] sera calculé pour i=nnp.
    else m = ieme;              // Si nécessaire np[ieme] donné séparément.
    mp = new int[m];            // mp[] est un tabeau auxiliaire temporaire.
    np[0]=1;  np[1]=2;  np[2]=3;  np[3]=5;    np[4]=7;      // Les premiers
    mp[0]=1;  mp[1]=4;  mp[2]=9;  mp[3]=5*5;  mp[4]=7*7;    // sont donnés.
    int i = 5;                  // i est le rang du prochain nombre premier.
    s=0;                        // On va éviter les multiples de 2, 3 et 5
    for(n=11; i<m; n=n+t[s]) {  // 11 13 17 19 23 29 31 37 41 43 47 49 ...
        for(int k=4;;k++) {     // Le nombre n a-t-il un diviseur premier ?
            int64_t j = np[k];           // On commence à j = np[4] = 7
            if( n == mp[k] ) break;      // Si n est multiple de np[k]
            if( j*j > int64_t(n) ) {     // Si aucun np[k] n'a fourni
                np[i] = n;               // un diviseur de n, alors 
                if(n>46340) mp[i]=maxi;  // n est premier : on l'archive
                else mp[i] = n*n;        // et on initialise son prochain 
                i = i+1;                 // multiple utilisable ensuite.
                break;
            }
            if( n > mp[k] ) {      // mp[k] : prochain multiple de np[k]
                if( mp[k] > maxi-int(2*j) ) mp[k] = maxi;  
                else mp[k] = mp[k] + int(2*j);
            }
        }                                     
        if(++s == 8) s=0;
    }
    delete[] mp;   // pour libérer la mémoire du tableau auxiliaire mp[]
    if(nnp == ieme) np[ieme] = maxi;
} // ► https://codes-sources.commentcamarche.net/source/102339-nombres-premiers

La différence semble être la manière de savoir si n est divisible par j:
a) La méthode "modulo" n%j == 0, simple à programmer, n'a pas besoin de mémoire auxiliaire, mais est malheureusement gourmande en temps calcul.
b) L'ingénieux code présenté par pgl10 n'est pas évident, mais environ trois fois plus rapide !

Pour compléter la comparaison, j'ajoute la fonction "PrimeList"
   CodeS-SourceS: Nombres premiers: PrimeList.
Elle est basée sur le Crible d'Ératosthène et donne la liste de nombre premiers jusqu'à une valeur N donnée: 
unsigned int PrimeList(unsigned int N,unsigned int *np) { // array of primes <= N
  unsigned int E=(N+1)/2,m=E,k=1;
  unsigned char *usv=new unsigned char[E],*usv_i;
  memset(usv,1,E);
  for (unsigned int i=1,e=3; e<=N; ++i,e+=2) if (*(usv_i=usv+i))
    for (unsigned int j=(N/e-1)/2; j>=i; --j) if (usv[j]) {usv_i[e*j]=0; --m;}
  np[0]=2;
  for (unsigned int e=1; e<E; ++e) if (usv[e]) np[k++]=(e<<1)|1;
  delete[] usv;
  return m; // nombre de nombres premiers
}
C'est la plus rapide mais aussi la plus gourmande en mémoire auxiliaire, surtout avec une très grande liste.

>Remarques sur le code PrimeList:
a) La liste obtenue ne contient pas 1 au début.
b) On pourrait diviser la mémoire auxiliaire usv par 8 en utilisants des "bits".
c) L'adapter au non traitement des multiples de 2, 3 et 5 semble plus difficile.

Le test dans Liste.cpp indique la mémoire auxiliaire employée en octets (en plus de la liste qui contient les nombres premiers demandés), et le temps utilisé en milisecondes: 
Division:
lst[10]=29, 0 oct, 0 ms
lst[100]=541, 0 oct, 0 ms
lst[1000]=7919, 0 oct, 0 ms
lst[10000]=104729, 0 oct, 2 ms
lst[100000]=1299709, 0 oct, 65 ms
lst[1000000]=15485863, 0 oct, 1858 ms
lst[10000000]=179424673, 0 oct, 53134 ms

prems:
lst[10]=29, 44 oct, 0 ms
lst[100]=541, 404 oct, 0 ms
lst[1000]=7919, 4004 oct, 0 ms
lst[10000]=104729, 40004 oct, 1 ms
lst[100000]=1299709, 400004 oct, 29 ms
lst[1000000]=15485863, 4000004 oct, 641 ms
lst[10000000]=179424673, 40000004 oct, 15200 ms

PrimeList:
lst[9]=29, 15 oct, 0 ms
lst[99]=541, 271 oct, 0 ms
lst[999]=7919, 3960 oct, 0 ms
lst[9999]=104729, 52365 oct, 0 ms
lst[99999]=1299709, 649855 oct, 6 ms
lst[999999]=15485863, 7742932 oct, 80 ms
lst[9999999]=179424673, 89712337 oct, 950 ms

 
Bonne lecture ...
 

Liens

CodeS-SourceS-pgl10: Nombres premiers
Nombres premiers: essais de division avec liste
CodeS-SourceS: Nombres premiers: PrimeList
 
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)