O prima idee de optimizare ar fi sa nu mai luam in calcul numerele pare pentru ca stim ca singurul numar prim par e {$2$}. Deci sa vedem noua varianta a programului:

p(pre). {@  //class PrimeNumbersSieve2@}
{@  final int MAXSIZE = 1000001;@}
{@  char[] p = new char[MAXSIZE];@}
{@ @}
{@  //p[i] == 0 if i is prime@}
{@  @}
{@  public int getTheNumber(int n) {@}
{@    int i, j, nr = 1;@}
{@    for (i = 3; i <= n; i += 2) {@}
{@      if (p[i] @}&#0061;&#0061;{@ 0) {@}
{@        nr++;@}
{@        for (j = i + i + i; j <= n; j += i << 1) {@}
{@          p[j] = 1;@}
{@        }@}
{@      }@}
{@    }@}
{@    return nr;@}
{@  }@}

== code(java) |
  //class PrimeNumbersSieve2
  final int MAXSIZE = 1000001;
  char[] p = new char[MAXSIZE];
 
  //p[i] == 0 if i is prime
 
  public int getTheNumber(int n) {
    int i, j, nr = 1;
    for (i = 3; i <= n; i += 2) {
      if (p[i] == 0) {
        nr++;
        for (j = i + i + i; j <= n; j += i << 1) {
          p[j] = 1;
        }
      }
    }
    return nr;
  }
==

Putem incerca o optimizare de memorie, pentru ca nu mai avem nevoie de elementele cu index par din sirul {$p$}. Acum semnificatia lui $p{~i~}$ s-a schimbat $p{~i~}$ fiind 0 daca $2*i+1$ e numar prim si $1$ daca nu.

p(pre). {@  // class PrimeNumbersSieve3 @}
{@  final int MAXSIZE = 1000000/2+1;@}
{@  char[] p = new char[MAXSIZE];@}
{@ @}
{@  //p[i] @}=={@ 0 if 2*i + 1 is prime@}
{@  @}
{@  public int getTheNumber(int n) {@}
{@    int i, j, nr = 1;@}
{@    for (i = 1; (i << 1) + 1 <= n; i += 1) {@}
{@      if (p[i] @}&#0061;&#0061;{@ 0) {@}
{@        nr++;@}
{@        for (j = i + i + i + 1; (j << 1) + 1 <= n; j += (i << 1) + 1) {@}
{@          p[j] = 1;@}
{@        }@}
{@      }@}
{@    }@}
{@    return nr;@}
{@  }@}

== code(java) |
  // class PrimeNumbersSieve3
  final int MAXSIZE = 1000000/2+1;
  char[] p = new char[MAXSIZE];
 
  //p[i] == 0 if 2*i + 1 is prime
 
  public int getTheNumber(int n) {
    int i, j, nr = 1;
    for (i = 1; (i << 1) + 1 <= n; i += 1) {
      if (p[i] == 0) {
        nr++;
        for (j = i + i + i + 1;
 
               (j << 1) + 1 <= n;
 
                  j += (i << 1) + 1) {
          p[j] = 1;
        }
      }
    }
    return nr;
  }
==

Urmatoarea optimizare va fi marcarea multiplilor numarului prim $i$ de la $i*i$ nu de la $2*i$ cum am facut in prima varianta sau de la $3*i$ cum am facut in a {$2$}-a. Aceasta optimizare este evidenta: orice numar prim compus multiplu de $i$ mai mic decat $i*i$ are un factor prim mai mic decat {$i$}, si acel factor l-a marcat mai devreme, deci nu are rost sa il marcam si la pasul {$i$}. Ideea aceasta este exact ideea ce se foloseste la rezolvarea problemei "Numere Prime":http://www.infoarena.ro/task/prim din arhiva infoarena. Sa vedem acum codul sursa: