Nombres premiers: Crible récursif

Télécharger le projet
Commenter

Description

Bonjour,

Dans une grande partie des logiciels qui recourent à la segmentation, on détermine le crible d'Ératosthène < N en précalculant les nombres premiers jusqu'à √N.

Cela m'à incité à écrire la fonction SieveRecur qui emprunte cette idée pour évaluer le crible récursivement: 
// calculate the sieve isPrime from isPrime[0] to isPrime[N]
void SieveRecur(uint N, bool *isPrime) { // len(isPrime) > N
  // avant le premier appel, isPrime[0..N] doit être initialisé à true
  if (N <= 3) {isPrime[0] = isPrime[1] = false; return;}
  uint R = sqrt(N);
  SieveRecur(R, isPrime);
  for (uint m, p = 2; p <= R; ++p)
    if (isPrime[p]) { // p is prime {
      for (m = p*p; m <= N-p; m += p) isPrime[m] = false;
      isPrime[m] = false;
    }
}

void Sieve0(uint N, bool *isPrime) { // len(isPrime) > N
  isPrime[0] = isPrime[1] = false;
  memset(isPrime+2, true, N-1);
  uint R = sqrt(N);
  for (uint p=2; p <= R; ++p)
    if (isPrime[p])
      for (uint q = p, Q = N/p; q <= Q; ++q) isPrime[p*q] = false;
} // 

bool *EratoD(uint N, bool *isPrime) {
  isPrime[0]=false; isPrime[1]=false; memset(isPrime+2,true,N-1);
  for (uint p=2; p*p<=N; ++p)
    if (isPrime[p])
      for (uint q=N/p; q>=p; --q)
        if (isPrime[q]) isPrime[p*q]=false;
  return isPrime;
}
Malheureusement, la fonction SieveRecur est à peine plus rapide que Sieve0 décrite dans mes articles précédents: 
SieveRecur:
N = 10, n = 4, t = 0 ms
N = 100, n = 25, t = 0 ms
N = 1000, n = 168, t = 0 ms
N = 10000, n = 1229, t = 0 ms
N = 100000, n = 9592, t = 0 ms
N = 1000000, n = 78498, t = 2 ms
N = 10000000, n = 664579, t = 92 ms
N = 100000000, n = 5761455, t = 1270 ms
N = 1000000000, n = 50847534, t = 15607 ms
Sieve0:
N = 10, n = 4, t = 0 ms
N = 100, n = 25, t = 0 ms
N = 1000, n = 168, t = 0 ms
N = 10000, n = 1229, t = 0 ms
N = 100000, n = 9592, t = 0 ms
N = 1000000, n = 78498, t = 3 ms
N = 10000000, n = 664579, t = 100 ms
N = 100000000, n = 5761455, t = 1347 ms
N = 1000000000, n = 50847534, t = 16263 ms
EratoD:
N = 10, n = 4, t = 0 ms
N = 100, n = 25, t = 0 ms
N = 1000, n = 168, t = 0 ms
N = 10000, n = 1229, t = 0 ms
N = 100000, n = 9592, t = 0 ms
N = 1000000, n = 78498, t = 3 ms
N = 10000000, n = 664579, t = 39 ms
N = 100000000, n = 5761455, t = 422 ms
N = 1000000000, n = 50847534, t = 4868 ms
Ce qui est déjà "pas si mal" !

On peut bien-sûr l'améliorer en évitant de traiter les multiples de quelques petits nombres premiers (2, 3, 5, ..).

Comme je l'ai signalé auparavant, la segmentation n'est pas à proprement parler un algorithme !
Mais plutôt une "simplification" de la gestion de la mémoire virtuelle.
Le jour où nos ordinateurs disposeront d'"assez" de mémoire (réelle), les "segmentations" n'auront plus de raison d'être.

En attendant, ces idées vont donc m'encourager à essayer de "segmenter" des algorithmes plus performants que ceux qui habituellement utilisés !

Bonne lecture ...
 

Liens

CodeS-SourceS: Nombres premiers
CodeS-SourceS: Nombres premiers bis
CodeS-SourceS: Nombres premiers: PrimeList
CodeS-SourceS: Nombres premiers: crible d'Eratosthène
(GitHub) Kim Wallisch: Segmented sieve of Eratosthenes
 
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)