Sa incercam o prima implementare a acestui algoritm (implementarile vor folosi limbajul java, dar sunt foarte usor transformabile in C/C++).

p(pre). {@  //class PrimeNumbersSieve1@}
{@  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 = 0;@}
{@    for (i = 2; i <= n; ++i) {@}
{@      if (p[i] @}&#0061;&#0061;{@ 0) {@}
{@        nr++;@}
{@        for (j = i + i; j <= n; j += i) {@}
{@          p[j] = 1;@}
{@        }@}
{@      }@}
{@    }@}
{@    return nr;@}
{@  }@}

== code(java) |
  //class PrimeNumbersSieve1
  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 = 0;
    for (i = 2; i <= n; ++i) {
      if (p[i] == 0) {
        nr++;
        for (j = i + i; j <= n; j += i) {
          p[j] = 1;
        }
      }
    }
    return nr;
  }
==

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: