Nombres premiers: Crible segmenté (A)

Télécharger le projet
Commenter

Description

Bonjour,

L'algorithme du crible segmenté semble être le plus rapide pour calculer des nombres premiers, surtout lorsqu'ils dépassent le milliard.

Le code présenté montre qu'on calcule d'abord, avec un algorithme classique, le crible des nombres premiers jusqu'à la racine carrée de N.
Ensuite, on détermine, segment par segment, les plus grands restants.

Voir CodeS-SourceS: Le crible d'Eratosthène classique.

Cette première version (A) s'inspire du code (non optimisé) de Kim Wallisch segmented_sieve.cpp, qui a des performances assez comparables. 
typedef int64_t i64;
typedef unsigned int uint;
const uint SS=32768; // SegmentSize
bool *seg=(bool*)malloc(SS),*ptC;

i64 SegmA(i64 N) {
  uint sqrtN=(uint)std::sqrt((double)N);
  i64 s=2,n=3,c=(N<2)?0:1; // c: quantité de premiers 
  ptC=(bool*)malloc(sqrtN+1);
  for(uint i=0; i<=sqrtN; ++i) ptC[i]=true;
  for(uint i=2; i*i<=sqrtN; ++i) // Crible d'Eratosthène classique
    if(ptC[i])
      for(uint q=sqrtN/i; q>=i; --q)
        if(ptC[q]) ptC[i*q]=false;
  std::vector<uint> pos,nxt;
  for(i64 a=0; a<=N; a+=SS) { // Segments
    for (uint i=0; i<SS; ++i) seg[i]=true;
    i64 b=min(a+SS-1,N);
    for(i64 ss=s*s; ss<=b; s++,ss=s*s)
      if(ptC[s]) {pos.push_back((uint)(s+s)); nxt.push_back((uint)(ss-a));}
    for(uint i=1; i<pos.size(); i++) {
      uint j=nxt[i];
      for(uint k=pos[i]; j<SS; j+=k) seg[j]=false;
      nxt[i]=j-SS;
    }
    while (n<=b) {
      if(seg[n-a]) c++; // n est un nombre premier
      n+=2;
    }
  }
  return c;
}

Mon (même) ordinateur donne l'output suivant: 
4/10, 0 ms
25/100, 0 ms
168/1000, 0 ms
1229/10000, 0 ms
9592/100000, 0 ms
78498/1000000, 0 ms
664579/10000000, 15 ms
5761455/100000000, 140 ms
50847534/1000000000, 1688 ms
455052511/10000000000, 22016 ms
4118054813/100000000000, 326547 ms

Et également: 203268793/4294709602, 8906 ms

Consultez le fichier Nombres premiers qui vous permet de comparer différents algorithmes.

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