Nombres premiers: PrimeList

Commenter

Contenu du snippet

Bonjour,

Jusqu’à maintenant, dans mes codes de nombres premiers, j’ai toujours affiché le nombre de nombres premiers créés. Cela permet une bonne vérification de l'algorithme utilisé et d’en donner les performances.

Prochainement, j’aurais besoin d’un tableau contenant les nombres premiers plus petits ou égal à un entier donné.

Comme beaucoup de logiciels utilisent les nombres premiers jusqu’à la racine carrée du "domaine" envisagé, je présente ici un code basé sur les entiers de 32 bits.

L’algorithme choisi correspond à celui de EratoOdd: 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef unsigned int uint;

uint *PrimeList(uint N,uint *NP) { // array of primes <= N
  uint E=(N+1)/2,np=E,k=0;
  unsigned char *usv=(unsigned char*)malloc(E),*usv_i;
  memset(usv,1,E);
  for (uint i=1,e=3; e<=N; ++i,e+=2) if (*(usv_i=usv+i))
    for (uint j=(N/e-1)/2; j>=i; --j) if (usv[j]) {usv_i[e*j]=0; --np;}
  uint *lst=(uint*)malloc(np*sizeof(uint));
  lst[k++]=2;
  for (uint e=1; e<E; ++e) if (usv[e]) lst[k++]=(e<<1)|1;
  free(usv);
  *NP=np;
  return lst;
}

int main() {
  printf("nPrimeList:n");
  uint *lst,np;
  for (uint N=10; N<=1000000000; N*=10) {
    clock_t t=clock();
    lst=PrimeList(N,&np);
    t=clock()-t;
    printf("nN=%u, np=%u, t=%u ms, ",N,np,1000*t/CLOCKS_PER_SEC);
    printf("lst=[%u,%u,...,%u,%u]",lst[0],lst[1],lst[np-2],lst[np-1]);
    free(lst);
  }
  getchar();
}
Avez-vous aperçu la petite astuce pour déterminer le nombre de premiers np en "décomptant" (--np) des multiples biffés ?
Cela n'est possible que parce que l'algo choisi est "radin": il ne supprime un élément qu'une seule fois.

L'exécution donne le résultat suivant: 
PrimeList:

N=10, np=4, t=0 ms, lst=[2,3,...,5,7]
N=100, np=25, t=0 ms, lst=[2,3,...,89,97]
N=1000, np=168, t=0 ms, lst=[2,3,...,991,997]
N=10000, np=1229, t=0 ms, lst=[2,3,...,9967,9973]
N=100000, np=9592, t=0 ms, lst=[2,3,...,99989,99991]
N=1000000, np=78498, t=4 ms, lst=[2,3,...,999979,999983]
N=10000000, np=664579, t=41 ms, lst=[2,3,...,9999973,9999991]
N=100000000, np=5761455, t=404 ms, lst=[2,3,...,99999971,99999989]
N=1000000000, np=50847534, t=3999 ms, lst=[2,3,...,999999929,999999937]
Remarquez qu'un array formé des nombres premiers jusqu’à un milliard (10⁹) occupe plus de 200 Mo !

En regardant ma boule de cristal, je vois que les performances de PrimeList vont encore s'améliorer.

Liens:
William Voirol: Nombres premiers
CodeS-SourceS: Le crible d'Eratosthène classique voir EratoOdd
CodeS-SourceS: Nombres premiers: Le crible avare A

Bonne lecture ...

Compatibilité : Version du 10 janvier 2017

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)