我们知道 3 以上的所有素数都可以使用以下方法生成：

6 * k + 1
6 * k - 1

然而，从上述公式生成的所有数字都不是素数。

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

为了消除这种情况，我使用了筛分法并删除了作为上述公式生成的数字的因子的数字。

使用事实：

如果一个数没有质因数，则称该数为质数。

1. 因为我们可以使用上面的公式生成所有素数。
2. 如果我们可以删除上述数字的所有倍数，我们就只剩下质数。

生成 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);

然而，这种方法确实能正确生成素数。这运行得更快，因为我们不需要检查我们在筛子中检查的所有数字。

我的问题是我是否遗漏了任何边缘情况？这会好很多，但我从未见过有人使用它。难道我做错了什么？

这种方法可以进一步优化吗？

采取boolean[]而不是ArrayList速度要快得多。

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

5 是根据您的条件生成的第一个数字。我们来看一下 25 以内生成的数字：

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

现在，当我们使用埃拉托色尼筛算法时，让我们看看这些相同的数字：

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

删除2后：

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

删除3后：

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

这和第一套是一样的！请注意，它们都包含 25，这不是质数。如果我们仔细想想，这是一个显而易见的结果。考虑任意 6 个连续数字的组：

6k - 3、6k - 2、6k - 1、6k、6k + 1、6k + 2

如果我们稍微考虑一下，我们会得到：

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

任意一组 6 个连续数字中，其中 3 个可被 2 整除，其中 2 个可被 3 整除。这些正是我们迄今为止删除的数字！所以：

你的算法只能使用6k - 1 and 6k + 1与埃拉托斯特尼筛法的前两轮完全相同。

与筛子相比，这也是一个相当不错的速度改进，因为我们不必添加所有这些额外的元素来删除它们。这解释了为什么你的算法有效以及为什么它不会错过任何案例；因为它和筛子完全一样。

无论如何，我同意一旦你生成了素数，你的boolean way is 迄今为止最快的。我已经使用你的设置了一个基准ArrayList方式，你的boolean[]方式，以及我自己的使用方式LinkedList and iterator.remove()（因为删除速度很快LinkedList。这是我的测试工具的代码。请注意，我运行了 12 次测试以确保 JVM 已预热，并且打印了列表的大小并更改了n试图阻止太多分支预测 https://stackoverflow.com/q/11227809/1768232优化。您还可以使用以下方法在所有三种方法中获得更快的速度+= 6在初始种子中，而不是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);
    }
  }
}

以及最近几次试验的结果：

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