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:

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

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

Codul sursa arata putin urat pentru ca nu lucram direct cu $i$ ci cu {$2*i+1$}, am mai facut optimizarea ce apare si in "mathworld":http://mathworld.wolfram.com/, nu parcurgem numerele pana la $n$ pentru marcarea multiplilor ci pana la $sqrt(n)$ lucru care e evident dupa cele explicate mai sus.
Ultima imbunatatire care o vom aduce este aceea de a folosi mai putina memorie. Cum pentru fiecare numar e necesara doar o informatie booleana, aceasta o putem tine intr-un bit, nu este necesar un char intreg. Sa vedem cum arata codul:

== code(java) |
  //class PrimeNumbersSieve5
  final int MAXSIZE = 100000000/2/8+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 * i) << 1) + (i << 1) <= n;
 
          i += 1) {
      if ((p[i >> 3] & (1 << (i & 7))) == 0) {
        for (j = ((i * i) << 1) + (i << 1);
 
              (j << 1) + 1 <= n;
 
               j += (i << 1) + 1) {
          p[j >> 3] |= (1 << (j & 7));
        }
      }
    }
    for (i = 1; 2 * i + 1 <= n; ++i)
 
         if ((p[i >> 3] & (1 << (i & 7))) == 0)
 
             nr++;
    return nr;
  }
==

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

Codul {@p[i >> 3] & (1 << (i & 7)) @}&#0061;&#0061;{@ 0@} testeaza daca al {@i@}-lea bit din sirul de biti e $0$ (deci daca {@2*i+1@} e prim). {@i >> 3@} e echivalent cu {@i / 8@} deci se gaseste pt bitul al {@i@}-lea in ce char e el stocat din sirul nostru de charuri. {@i & 7@} e echivalent cu {@i % 8@} ca sa aflam pe ce bit al charului e stocat numarul prim {@i@}.

Codul folosit pentru testare e:

== code(java) |
  public static void main(String[] arg) {
    double tick = System.currentTimeMillis();
    for (int i = 0; i < 10; ++i) {
      System.out.println("Run " + i
    + " result: "+
      new PrimeNumbersSieve1().
      getTheNumber(1000000));
    }
    System.out.println(" 10 runs of "
  + "PrimeNumbersSieve1()."
  + "getTheNumber(1000000) "
  + "lasted: "
  + (System.currentTimeMillis()
  - tick)
  * 1e-3 + " seconds");
  }
==

p(pre). {@public static void main(String[] arg) {@}
{@    double tick = System.currentTimeMillis();@}
{@    for (int i = 0; i < 10; ++i) {@}
{@      System.out.println("Run " + i @}
{@    + " result: "+@}
{@      new PrimeNumbersSieve1().@}
{@      getTheNumber(1000000));@}
{@    }@}
{@    System.out.println(" 10 runs of "@}
{@  + "PrimeNumbersSieve1()." @}
{@  + "getTheNumber(1000000) " @}
{@  + "lasted: " @}
{@  + (System.currentTimeMillis() @}
{@  - tick) @}
{@  * 1e-3 + " seconds");@}
{@  }@}
 
 

S-a rulat fiecare cod de $10$ ori pentru a da ocazia optimizarilor Just In Time din java sa isi faca treaba.