Nombres premiers

Soyez le premier à donner votre avis sur cette source.

Vue 1 024 fois - Téléchargée 76 fois

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
 

Codes Sources

A voir également

Ajouter un commentaire

Commentaire

pgl10
Messages postés
310
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
6 juillet 2019
1 -
Bonjour M. William Voirol,
Les trois fonctions Division, prems et PrimeList n'ont pas le même appel et ont une programmation différente. Cela permet au visiteur de faire le choix qu'il souhaite, c'est pourquoi il est très intéressant d'en avoir fait cette comparaison.
Bravo et merci.
Peut-être que d'autres codes pour la même utilisation vont être référencés ou publiés. Mais il faut noter que l'emploi de la liste des n premiers nombres premiers pour une valeur élevée mais limitée du nombre n est une circonstance moins fréquente que celle du crible classique d'Ératosthène, lequel permet assez facilement une limite encore beaucoup plus grande pour un emploi voisin mais différent.

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.