Prime Number Sieving Algorithm Last semester in my Masters Program I developed this code for sieving. My professor wants me to write a report that he might use locally within the school, but I feel like I've done nothing that new, despite coming up with my algorithm without doing any research other than the bare numbers.

Essentially it skips over a large percentage of numbers (I estimate about 66%). It skips all factors of 2 and 3. The first loop throws in primes and potential primes through a modified formula of 6k+-1. The second nested loop takes the outer prime numbers and finds all multiples. 

The inner if statement skips numbers as well - if the number is a factor of 3, it skips ahead. For instance if B = 13, B+2 = 15%3 = 0, then B jumps straight to 17. I've found this method to be faster for some reason than accessing the array every b+=2; and switching the boolean. Unfortunately, I wish I could find a way to make it more efficient (I may be able to use an additional counter to just figure out when the number is going to fall on a five or three).

Psuedo-code as follows (of course this implementation is different, but follows similar principles):


Initialize list with initial values (2,3).
Use the formula 6k±1 where k = 1 and must increment by 1. Store values to list.
Compute step 2 up to a product n, where n > 7 if k = 1.
Starting with x=5, remove all products of x*y (to n), where y starts at x and
increments to the next number in the list as x remains the same.
Repeat step four by assigning x to the next number in the list - stop when x*y > N.
Final step: We must remove all factors of the square of every prime number (25, 49)


Is this any decent, or is my implementation really slow?

//-----------------------------------------------------------------
//
//  Class:   SixSieve.java
//
//  Author:  Alex Lieberman
//
//  Purpose: Finds all prime numbers up to a specified
//           maxNumber and marks them as true in the boolean array.
//
//-----------------------------------------------------------------

public class SixSieve

 {

  public static void main (String[] args) 

  { 

   int maxNumber = 1000;

   boolean[] Numbers = new boolean [maxNumber];

   Numbers[2] = true;
   Numbers[3] = true;

   int num = Numbers.length;

   //----------------------------
   //
   //  The following loop finds 
   //  potential primes and primes.
   //
   //----------------------------

   for (int i = 5, j = 7; i &lt; num; i+=6, j+=6)

    {

     Numbers[i] = true;

     if (j &lt; num)       

      Numbers[j] = true;

    }

   //----------------------------
   //
   //  The following loop eliminates
   //  non-primes (multiples of everything
   //  in the previous loop).
   //
   //----------------------------

   for (int a = 5; a*a &lt;= num; a+=2) 

    {

     if (Numbers[a]) 

      {

       for (int b = a; b*a &lt;= num; ) 

        {

         Numbers[b*a] = false;

         if ((b+2)%3 == 0)

          b+=4;

         else

          b+=2;

        }

      }   

    }

    System.out.println("Done");

   //----------------------------
   //
   //  The following loop prints
   //  all the primes found.
   //
   //----------------------------

    for (int i = 0; i &lt; num; i++) 

     {

      if (Numbers[i] == true)

       System.out.print(i + " ");

     }

  }

 }
I'd rename Numbers to isPrime
num is not needed. maxNumber serves the same purpose.
Termination condition in the elimination loops must be &lt;, not &lt;=. With an unfortunate value of maxNumber, the latter would make an illegal access.
An inner elimination loop can be shortened to

for (int b = a; b*a &lt;= num; ) {
    isPrime[b*a] = false;
    b += 2;
    if (b%3 == 0)
        b+=2;
}

It is worth noticing that i+=6, j+=6 serves the same purpose as if (b%3 == 0) b+=2. Better be unified (it looks like an expensive modulo operator can be avoided). I'd seriously consider splitting each loop into two independent loops with increment 6.
Finally, the implementation is not slow (other than using %), but it is not any faster than a standard sieve.