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

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

1. My optimized code: 4 seconds N = 1,000,000,000

2. My original code: 7 seconds N = 1,000,000,000

3. Standard Sieve-of-Eratosthenes: 16 seconds N = 1,000,000,000

My original thread with same pseudo-code is here - Prime Number Sieving Algorithm - 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).

Code:

1. My optimized code: 4 seconds N = 1,000,000,000

2. My original code: 7 seconds N = 1,000,000,000

3. Standard Sieve-of-Eratosthenes: 16 seconds N = 1,000,000,000

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

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 two up to a product \$n\$, where \$n > 7\$ if \$k = 1\$.
4. 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.
5. Repeat step four by assigning \$x\$ to the next number in the list. Stop when \$x \times y > n\$.
6. Final step: We must remove all multiples of the square of every prime number \$(25, 49)\$

public class SixesSieve3
{
    public static void main(String[] args) {
        // maxNumber must be an even number
        int maxNumber = 1000;
        boolean[] isPrime = new boolean[maxNumber];
        isPrime[2] = true;
        isPrime[3] = true;
        // the for-loop below loads the array with potential primes in a manner
        // according to 6k+1, 6k-1
        for (int possiblePrime1 = 5, possiblePrime2 = 7; 
        possiblePrime1 < maxNumber; possiblePrime1 += 6, possiblePrime2 += 6) {
            isPrime[possiblePrime1] = true;
            if (possiblePrime2 < maxNumber) {
                isPrime[possiblePrime2] = true;
            }
        }
        // the for-loop below removes all non-primes from the equation
        for (int prime = 5; prime * prime <= maxNumber; prime += 2) {
            // the if-statement below skips the testing of all non-prime numbers
            if (isPrime[prime]) {
                for (int secondPrime = prime, square = prime * prime; secondPrime
                        * prime <= maxNumber;) {
                    // if the product of 'prime' and 'secondPrime' equals
                    // 'square'
                    if (secondPrime * prime == square && square < maxNumber / 2) {
                        // searches for all multiples of square that may exist in
                        // array
                        while (true) {
                            if (square <= maxNumber) {
                                isPrime[square] = false;
                                square += (prime * prime * 2);
                            }
                            else {
                                secondPrime += 2;
                                break;
                            }
                        }
                    }
                    // if 'prime' and 'secondPrime' are not equal to square
                    // then search for all multiples of 'prime' by 'secondPrime'
                    else {
                        isPrime[secondPrime * prime] = false;
                        secondPrime += 2;
                        while (!isPrime[secondPrime]) {
                            secondPrime += 2;
                        }
                    }
                }
            }
        }
        for (int printPrimes = 0; printPrimes < maxNumber; printPrimes++) {
            if (isPrime[printPrimes]) {
                System.out.println(printPrimes + " ");
            }
        }
    }
}

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 two up to a product \$n\$, where \$n > 7\$ if \$k = 1\$.
4. 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.
5. Repeat step four by assigning \$x\$ to the next number in the list. Stop when \$x \times y > n\$.
6. 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 < maxNumber; i+=6, j+=6) {
     isPrime[i] = true;
     if (j < maxNumber)        
      isPrime[j] = true;
    }

   for (int a = 5; a*a <= maxNumber; a+=2) {
     if (isPrime[a]) {
  
       for (int b = a, z = a*a; b*a <= maxNumber; ) {
        if(b*a == z && z < maxNumber/2) {
         while (true){
           if (z <= 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 < maxNumber; i++) {
      if (isPrime[i])
       System.out.print(i + " ");
    }
  }
 }