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 ...
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.