for (i = 2; i <= maxsize; i++)
     if (!at[i])
       for (j = i + i; j <= maxsize; j += i)

          at[j]=1; //marcãm toþi multipli lui i ca fiind numere prime

          at[j]=1; //marcam toti multipli lui i ca fiind numere prime

}
==

Observăm că jumătate din timpul folosit de noi la preprocesare este pierdut cu numerele pare. Marcându-le de la început vom putea ignora numerele pare în preprocesare:
==code(cpp)|
#define maxsize 10000000
char at[maxsize];
int n;
int isPrime(int x){
  return (!at[x]) ;
}
void sieve(){
  int i, j;
  memset(at,0,sizeof(at));
  for (i = 4; i <= maxsize; i += 2)
     at[i] = 1;
  for (i = 3; i <= maxsize; i += 2)
     if (!at[i])
       for (j = i + i + i; j <= maxsize; j += i + i)
          at[j] = 1;
}
==
 
La marcarea multiplilor numărului prim $i$ toate numerele până la $i · i$ au fost deja marcate deoarece $i · i$ este cel mai mic număr care nu este divizibil cu numere naturale mai mici sau egale cu $i - 1$, deci, avem o a treia versiune a programului:
==code(cpp)|
void sieve(){
  int i, j;
  memset(at,0,sizeof(at));
  for (i = 4; i <= maxsize; i += 2)
     at[i] = 1;
  for (i = 3; i <= maxsize; i += 2)
     if (!at[i])
       for (j = i * i; j <= maxsize; j += i + i)
          at[j] = 1;
}
==
 
Ultima optimizare este optimizarea spaţiului necesar. Într-un tip de date char putem împacheta opt valori logice şi punând un test suplimentar în metoda isPrime putem elimina şi numerele pare, astfel vom avea nevoie de un spaţiu de 16 ori mai mic.
 
==code(cpp)|
#define maxsize 10000000
 
char at[maxsize/16];
int n;
 
int isPrime(int x) {
  if (!(x & 1))
     if (x==2) return 0 ;
     else return 1 ;
     else return (at[((x - 3) >> 1) >> 8] &
                       (1 << (((x - 3) >> 1) & 7))) ;
}
void sieve() {
  int i, j;
  memset(at, 0, sizeof(at)) ;
  for (i = 3; i <= maxsize; i += 2)
     if (!at[((i - 3) >> 1) >> 8] &
                         (1 << (((i - 3) >> 1) & 7)))
       for (j=i * i ; j <= maxsize ; j += i + i)
          at[((i - 3) >> 1) >> 8] |=
                       (1 << (((i - 3) >> 1) & 7))) ;
}
==
 
h2. Concluzie
 
Asemenea optimizări ca şi cele prezentate în cadrul acestui articol se pot dovedi foarte utile în unele cazuri, dar ele fac
programul ilizibil, tocmai din acest motiv, asemenea trucuri trebuie aplicate numai în locurile critice ale codurilor sursă pentru a
duce la o creştere semnificativă de viteză a aplicaţiilor şi trebuie documentate foarte bine, mai ales dacă se doreşte sau este necesar ca alt programator să poată lucra cu codul respectiv mai târziu.
 
h3. Bibliografie
 
# James A. Storer, An Introduction to Data Structures and Algorithms, Springer Verlag, 2001
# T. H. Cormen, C. E. Leiserson, R. R. Rivest, Introducere în algoritmi, Editura Computer Libris Agora, 2000
# http://www.aggregate.org/MAGIC/
# http://www.topcoder.com/tc