A fast approach to prime number sieving (non-threaded array) I am posting this question for input on comparisons between other sieving methods and opinions on what I have discovered. I believe this might be the fastest (singular, non-threaded) array implementation of prime sieving to date, correct me if I am wrong.

My rudimentary benchmark tests stand as follows:


My optimized code: 4 seconds   N = 1,000,000,000
My original code: 7 seconds   N = 1,000,000,000
Standard Sieve-of-Eratosthenes: 16 seconds  N = 1,000,000,000


I have seen PrimeSieve and as I understand it utilizes better means to compute faster, but as it seems - it must dump the data somewhere and retrieve it to utilize it again, because it cycles the computations through the cache only.

My original thread with same pseudo-code is here, however, my original Java code did not match the pseudo-code I developed (but essentially performed similar functions at a lesser speed and easier complexity to code).

Pseudo-code as follows:


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 two up to a product \$n\$, where \$n &gt; 7\$ if \$k = 1\$.
Starting with \$x = 5\$, remove all products of \$x \times y\$ (up 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 \times y &gt; n\$.
Final step: We must remove all factors of the square of every prime number \$(25, 49)\$




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

public class SixesSieve {    
  public static void main (String[] args) { 

   int maxNumber = 1000000000;
   boolean[] isPrime = new boolean [maxNumber];
   isPrime[2] = true;
   isPrime[3] = true;

   for (int i = 5, j = 7; i &lt; maxNumber; i+=6, j+=6) {
     isPrime[i] = true;
     if (j &lt; maxNumber)       
      isPrime[j] = true;
    }

   for (int a = 5; a*a &lt;= maxNumber; a+=2) {
     if (isPrime[a]) {

       for (int b = a, z = a*a; b*a &lt;= maxNumber; ) {
        if(b*a == z &amp;&amp; z &lt; maxNumber/2) {
         while (true){
           if (z &lt;= maxNumber) {
            isPrime[z] = false; 
            z = z+(a*a*2);
           }
           else
            {b+=2; break;}
           }
         }   
        else {
         isPrime[b*a] = false;
         b+=2;
         while (!isPrime[b])
         {b+=2;}    
        }  
       }
      }   
    }

    for (int i = 0; i &lt; maxNumber; i++) {
      if (isPrime[i])
       System.out.print(i + " ");
    }
  }
 }
Just some minor comments to the code style. Let's start with your fileheader...in these times and days it should be unnecessary. First it doesn't make sense to have the file/classname in the comment, it's only something that will get out of date because refactoring can't reach it. Second, the other parts should be in the JavaDoc of the class.



Variable names. I know it is hard to find good names for such...mathematical stuff, but try to find them. 'a', 'b', 'z' are meaningless. It is hard to read the code if variables have meaningless names.



The code formatting is partly a bloody mess. If you use an IDE, make use of these formatting features. It is so much easier to read code if it is well formatted.

First, don't omit braces, even if it is just a one line 'if' or 'for' block. Second, be consistent about your brace style, and be consequent.



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


I still don't understand why the Java compiler does allow this. This is not a "cast", this is a hack in the best of cases.

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