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.
//
//------------------------

-
I'd rename Numbers to isPrime

-
num is not needed. maxNumber serves the same purpose.

-
Termination condition in the elimination loops must be

-
An inner elimination loop can be shortened to

for (int b = a; b*a <= 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.

StackExchange Code Review Q#54591, answer score: 6