How do I generate Primes Using 6*k +- 1 rule

Question

We know that all primes above 3 can be generated using:

6 * k + 1
6 * k - 1

However we all numbers generated from the above formulas are not prime.

For Example:    
6 * 6 - 1 = 35 which is clearly divisible by 5.

To Eliminate such conditions, I used a Sieve Method and removing the numbers which are factors of the numbers generated from the above formula.

Using the facts:

A number is said to be prime if it has no prime factors.

1. As we can generate all the prime numbers using the above formulas.
2. If we can remove all the multiples of the above numbers we are left with only prime numbers.

To generate primes below 1000.

ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
int n = 1000;
for (int i = 1; i <= (n / 6) ; i++) {
//get all the numbers which can be generated by the formula
    int prod6k = 6 * i;
    primes.add(prod6k - 1);
    primes.add(prod6k + 1);
}
for (int i = 0; i < primes.size(); i++) {
    int k = primes.get(i);
    //remove all the factors of the numbers generated by the formula
    for(int j = k * k; j <= n; j += k)//changed to k * k from 2 * k, Thanks to DTing
    {           
        int index = primes.indexOf(j); 
        if(index != -1)
            primes.remove(index);
    }
}
System.out.println(primes);

However, this method does generate the prime numbers correctly. This runs in a much faster way as we need not check for all the numbers which we do check in a Sieve.

My question is that am I missing any edge case? This would be a lot better but I never saw someone using this. Am I doing something wrong?

Can this approach be much more optimized?

---

Taking a boolean[] instead of an ArrayList is much faster.

int n = 100000000;
boolean[] primes = new boolean[n + 1];
for (int i = 0; i <= n; i++)
    primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
    int prod6k = 6 * i;
    primes[prod6k + 1] = true;
    primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
    if (primes[i]) {
        int k = i;
        for (int j = k * k; j <= n && j > 0; j += k) {
               primes[j] = false;
        }
      }
}
for (int i = 0; i <= n; i++)
    if (primes[i]) 
        System.out.print(i + " ");

Answer 1

5 is the first number generated by your criteria. Let's take a look at the numbers generated up to 25:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

Now, let's look at these same numbers, when we use the Sieve of Eratosthenes algorithm:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

After removing 2:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

After removing 3:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

This is the same as the first set! Notice they both include 25, which is not prime. If we think about it, this is an obvious result. Consider any group of 6 consecutive numbers:

6k - 3, 6k - 2, 6k - 1, 6k, 6k + 1, 6k + 2

If we factor a little, we get:

3*(2k - 1), 2*(3k - 1), 6k - 1, 6*(k), 6k + 1, 2*(3k + 1)

In any group of 6 consecutive numbers, three of them will be divisible by two, and two of them will be divisible by three. These are exactly the numbers we have removed so far! Therefore:

Your algorithm to only use 6k - 1 and 6k + 1 is exactly the same as the first two rounds of the Sieve of Erathosthenes.

It's a pretty nice speed improvement over the Sieve, too, because we don't have to add all those extra elements just to remove them. This explains why your algorithm works and why it doesn't miss any cases; because it's exactly the same as the Sieve.

---

Anyway, I agree that once you've generated primes, your boolean way is by far the fastest. I have set up a benchmark using your ArrayList way, your boolean[] way, and my own way using LinkedList and iterator.remove() (because removals are fast in a LinkedList. Here's the code for my test harness. Note that I run the test 12 times to ensure that the JVM is warmed up, and I print the size of the list and change the size of n to attempt to prevent too much branch prediction optimization. You can also get faster in all three methods by using += 6 in the initial seed, instead of prod6k:

import java.util.*;

public class PrimeGenerator {
  public static List<Integer> generatePrimesArrayList(int n) {
    List<Integer> primes = new ArrayList<>(getApproximateSize(n));
    primes.add(2);// explicitly add
    primes.add(3);// 2 and 3

    for (int i = 6; i <= n; i+=6) {
      // get all the numbers which can be generated by the formula
      primes.add(i - 1);
      primes.add(i + 1);
    }

    for (int i = 0; i < primes.size(); i++) {
      int k = primes.get(i);
      // remove all the factors of the numbers generated by the formula
      for (int j = k * k; j <= n; j += k)// changed to k * k from 2 * k, Thanks
                                         // to DTing
      {
        int index = primes.indexOf(j);
        if (index != -1)
          primes.remove(index);
      }
    }
    return primes;
  }

  public static List<Integer> generatePrimesBoolean(int n) {
    boolean[] primes = new boolean[n + 5];
    for (int i = 0; i <= n; i++)
      primes[i] = false;
    primes[2] = primes[3] = true;

    for (int i = 6; i <= n; i+=6) {
      primes[i + 1] = true;
      primes[i - 1] = true;
    }

    for (int i = 0; i <= n; i++) {
      if (primes[i]) {
        int k = i;
        for (int j = k * k; j <= n && j > 0; j += k) {
          primes[j] = false;
        }
      }
    }

    int approximateSize = getApproximateSize(n);
    List<Integer> primesList = new ArrayList<>(approximateSize);
    for (int i = 0; i <= n; i++)
      if (primes[i])
        primesList.add(i);

    return primesList;
  }

  private static int getApproximateSize(int n) {
    // Prime Number Theorem. Round up
    int approximateSize = (int) Math.ceil(((double) n) / (Math.log(n)));
    return approximateSize;
  }

  public static List<Integer> generatePrimesLinkedList(int n) {
    List<Integer> primes = new LinkedList<>();
    primes.add(2);// explicitly add
    primes.add(3);// 2 and 3

    for (int i = 6; i <= n; i+=6) {
      // get all the numbers which can be generated by the formula
      primes.add(i - 1);
      primes.add(i + 1);
    }

    for (int i = 0; i < primes.size(); i++) {
      int k = primes.get(i);
      for (Iterator<Integer> iterator = primes.iterator(); iterator.hasNext();) {
        int primeCandidate = iterator.next();
        if (primeCandidate == k)
          continue; // Always skip yourself
        if (primeCandidate == (primeCandidate / k) * k)
          iterator.remove();
      }
    }
    return primes;
  }

  public static void main(String... args) {
    int initial = 4000;

    for (int i = 0; i < 12; i++) {
      int n = initial * i;
      long start = System.currentTimeMillis();
      List<Integer> result = generatePrimesArrayList(n);
      long seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tArrayList Seconds: " + seconds);

      start = System.currentTimeMillis();
      result = generatePrimesBoolean(n);
      seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tBoolean Seconds: " + seconds);

      start = System.currentTimeMillis();
      result = generatePrimesLinkedList(n);
      seconds = System.currentTimeMillis() - start;
      System.out.println(result.size() + "\tLinkedList Seconds: " + seconds);
    }
  }
}

And the results of the last few trials:

3432    ArrayList Seconds: 430
3432    Boolean Seconds: 0
3432    LinkedList Seconds: 90
3825    ArrayList Seconds: 538
3824    Boolean Seconds: 0
3824    LinkedList Seconds: 81
4203    ArrayList Seconds: 681
4203    Boolean Seconds: 0
4203    LinkedList Seconds: 100
4579    ArrayList Seconds: 840
4579    Boolean Seconds: 0
4579    LinkedList Seconds: 111