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

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 + " ");

}

}

}

-
Maybe you use as a base the Matrix formulae in this "Genesis 11" Paper. I would not know how to do it myself. I have no idea about creating algorithms –  user77898 Jun 18 '14 at 9:08
Can anyone provide insight as to the time complexity? I've found it to be quite fast but I think I got the time complexity wrong. –  Alex Lieberman Jun 18 '14 at 10:27
I don't think I use the matrix formula. I have dozens of spreadsheets and my formula is based on a very simple skipping. –  Alex Lieberman Jun 18 '14 at 10:50
Perhaps CS SE would be a good place to look for algorithmic analysis? –  awksp Jun 18 '14 at 16:57
@AlexLieberman, please see this Meta post about iterative review. It's the community consensus that such edits should either be an answer to your own question, or a new question. It depends on whether or not you would like to have your new code reviewed. I have rolled back the last edit. –  RubberDuck Jun 19 '14 at 14:41

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

-
I agree with half of your statements - although I don't think splitting the loops would work. Additionally, I have done speed tests and I do find it to be faster than a standard implementation of Sieve of Eratosthenes. Takes about 1/3 the time, although that may have been a bad code selection. –  Alex Lieberman Jun 18 '14 at 9:56
As for the code referring to maxNumber... I added that last as an after thought so people wouldn't need to change array size directly and forgot to look for redundancy. –  Alex Lieberman Jun 18 '14 at 10:47

As there has already been said something on newlines and braces I will just highlight the "normal " 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 fields, methods and variables is camelCase. This means they usually start with a lowercase letter:

Numbers --> numbers

-
Thank you. I'm fairly new to coding. Appreciate your comments. –  Alex Lieberman Jun 18 '14 at 9:59

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:

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.

-
It seems to be more effective for me with higher integers. Testing up nine decimal places I found on my computer it took about seven and a half seconds compared to over fifteen seconds for eratosthenes that I tried. –  Alex Lieberman Jun 18 '14 at 13:07
It does seem to get better as the target number gets larger. Testing with 100,000,000: Yours: (775179245ns) Sieve: (1739788775ns) –  iismathwizard Jun 18 '14 at 13:19
@user3750870 i'd be interested in this being written using BigNum or some similar library for computation of numbers exceeding 2^32. This seems to be fairly effective at sieving through for primes. Nice work! –  iismathwizard Jun 18 '14 at 13:23

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.

-
this is a very c#-ish way of placing braces, why not go for full "java-conventions" ? –  Vogel612 Jun 18 '14 at 7:53
I haven't moved/added/removed braces. Not quite sure what the usual Java convention is - are you refering to oracle.com/technetwork/java/codeconventions-150003.pdf ? –  Josay Jun 18 '14 at 7:58
correct. see page 10 for a code-sample with braces placed as egyptian braces ;O) –  Vogel612 Jun 18 '14 at 8:03
@Vogel612 He's respecting OP coding style, which is important IMHO. Op is consistent in his code. There is probably a coding style convention in his school ( I had one and it was exactly like this answer even for Java). –  Marc-Andre Jun 18 '14 at 20:15

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.

-