Prime Number Sieving Algorithm

Question

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):

1. Initialize list with initial values (2,3).
2. Use the formula 6k±1 where k = 1 and must increment by 1. Store values to list.
3. Compute step 2 up to a product n, where n > 7 if k = 1.
4. 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.
5. Repeat step four by assigning x to the next number in the list - stop when x*y > N.
6. 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 < num; i+=6, j+=6)

    {

     Numbers[i] = true;

     if (j < num)       

      Numbers[j] = true;

    }

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

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

    {

     if (Numbers[a]) 

      {

       for (int b = a; b*a <= 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 < num; i++) 

     {

      if (Numbers[i] == true)

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

     }

  }

 }

Answer 1

• I'd rename Numbers to isPrime

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

• Termination condition in the elimination loops must be <, not <=. 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 <= 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.

Answer 2

As there has already been said something on newlines and braces I will just highlight the "normal java" way of placing braces. As I highlighted in multiple answers of mine, the usual way is to place the opening brace on the same line as the opening statement and the closing brace on a separate line.

for (int i = 0; i < num; i++) 

 {

  if (Numbers[i] == true)

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

 }

code like this becomes:

for (int i = 0; i < num; i++) {
    if(Numbers[i] == true)
        System.out.println(i + " ");
}

And in this short code-sample there are again 3 things I want to put out a comment on:

Braces:

Single operation if-statements should have braces placed, even though they are not required. Why? Have you heard of apple's goto fail; bug? They forgot to place the braces and broke a core functionality of iOS.

    if(Numbers[i] == true)
        System.out.println(i + " ");

And one more line won't really hurt you, will it?

if(Numbers[i] == true) {
    System.out.println(i + " ");
}

If-Conditions:

Your Numbers[i] contains true. Why not evaluate that directly??

if(Numbers[i] == true)

is actually exactly the same as the following, given Numbers is of type boolean[]

if(Numbers[i])

Naming-Conventions:

the Naming convention for java fields, methods and variables is camelCase. This means they usually start with a lowercase letter:

Numbers --> numbers

Answer 3

Your implementation is really strange however it seems to come up with good results. I was interested in your claim about the computation time being a third of Sieve of Eratosthenes.

After testing against this claim (and i did it properly: had a loop before either of the methods executed to get the JVM warmed up) here are my personal results:

1. Your method: 97779ns
2. Sieve of Eratosthenes: 98933ns

This was running against 1000 integers.

Note: I did not include time for printing out the integers as Console writing is slow and unnecessary in terms of calculating the values.

int N = maxNumber; //from the earlier sieve implementation

// initially assume all integers are prime
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++) {
    isPrime[i] = true;
}

// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {

    // if i is prime, then mark multiples of i as nonprime
    // suffices to consider multiples i, i+1, ..., N/i
    if (isPrime[i]) {
        for (int j = i; i*j <= N; j++) {
            isPrime[i*j] = false;
        }
    }
}

This was the Sieve code that I used (not my own).

I wouldn't say that it's much faster in this particular instance and that makes sense especially since it seems that you merely optimized the original sieve. I would say that the time complexity would match that of the original sieve; however, time complexities like this are hard to compute especially since it relies on a property of numbers that, at the moment, we don't have a clean way of calculating the behaviour over a set interval.

One value for the time complexity (assuming that your implementation closely models or only optimizes a little the computation time) would be O(n log(log(n))) since the prime harmonics approach log(log(n)). (Sieve of Erathosthenes)

I would guess that at worst case, your algorithm approaches the aforementioned value.

Answer 4

Before anything : your code looks nice and seems to be properly commented which is a good point. It could have been a good idea to give a pointer to some reference (wikipedia or anything else) as your implementation does not seem to rely on the usual sieve but on some kind of optimisation of it.

This being said, from my point of view, a bit too long as you are using too many blank lines and too many lines for comment. There is only so much text I can fit on my screens, I'd rather read this :

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

        // Finding potential primes and primes
        for (int i = 5, j = 7; i < num; i+=6, j+=6)
        {
            Numbers[i] = true;
            if (j < num)
                Numbers[j] = true;
        }

        // Elimination of non-primes (multiples of everything in the previous loop)
        for (int a = 5; a*a <= num; a+=2)
        {
            if (Numbers[a])
            {
                for (int b = a; b*a <= num; )
                {
                    Numbers[b*a] = false;
                    if ((b+2)%3 == 0)
                        b+=4;
                    else
                        b+=2;
                }
            }
        }

        System.out.println("Done");

        // Printing the primes
        for (int i = 0; i < num; i++)
        {
            if (Numbers[i] == true)
                System.out.print(i + " ");
        }
    }
}

Everything else I was about to say has just been said by vnp.

Answer 5

Just a tiny note (everything else has been covered already), which has got pretty long. It's mostly arguing against the root of all evil.

Numbers[b*a] = false;

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

    b+=4;

else

    b+=2;

(expect for the first) are a premature optimization, which may indeed be pessimization. You're avoiding one third of memory stores at the expense of

• a modulus operation
• a less regular memory access pattern
• longer code

The modulus operation is rather obvious. Normally, it takes ages (tens of cycles), but with known small modulus it may get optimized nicely like e.g. here.

The less regular memory access pattern is not that obvious. It may cost quite some time, too, I don't know how well the prefetchers can handle it.

A longer code may be slower simply because of it being longer.

In the end the complicated code may be way slower than the simpler one.

This all said, I'd recommend leaving all non-essential optimizations out unless you know that they're really needed and really helpful. Just do

Numbers[b*a] = false;
b+=2;

and you'll be fine.