在 Java 中，确定单个数字是否为 2 到 2,147,483,647 之间的数字的最有效方法是什么？

Question

作为 Java 程序员，我们始终可以使用 BigInteger isProbablePrime() 方法或手动将所有素数存储在 HashMap 中。这个问题是关于在 Java 中使用数据结构和自定义算法确定单个数字是否为 2 到 2,147,483,647 之间的数字的素数的最有效方法。

我认为最有效的方法是如果数字很小或偶数，则快速返回结果，然后只检查奇数素数值。在我的研究中，使用埃拉托斯特尼筛法部分生成素数直至平方根应该是最有效的方法。现在通过简单的搜索，我还发现也可以使用 Sundaram 筛法或 Atkin 筛法来代替，但我不确定 Integer.MAX_VALUE 是否在渐近有效的范围内。

我想知道还有比这更有效的生成素数的方法吗？ （见下面的代码）

public static boolean PrimeTime(int num) {
  if(num < 4) {
    return true;
  }
  if(num % 2 == 0) {
    return false;
  }
  int max = (int) Math.sqrt(num);
  boolean[] notPrimes = new boolean[max];
  if(8 < max) {
    int findMax = (int) Math.sqrt(notPrimes.length);
    for(int odd = 3; odd <= findMax; odd = odd + 2) {
      if(!notPrimes[odd - 1]) {
        for(int i = odd * 3 - 1; i < notPrimes.length; i = i + 2 * odd) {
          notPrimes[i] = true;
        }
      }
    }
  }
  for(int i = 2; i < notPrimes.length; i = i + 2) {
    if(!notPrimes[i]) {
      if(num % (i + 1) == 0) {
        return false;
      }
    }
  }
  return true;
}

根据 David Conrad 的提示，我将 boolean[] 与 BitSet 进行了比较。我的基准测试（使用黑洞和状态）显示，搜索最高素数 Integer.MAX_VALUE 的 boolean[] 吞吐量更高（多 40%），boolean[] 的吞吐量为 8218,042 ± 735,978 ops/s，boolean[] 的吞吐量为 5729,806 ± 271,468 ops/ s 代表 BitSet。

Answer 1

isProbablePrime() 方法使用 Miller-Rabin，使用确定性 40 会是一个更快的算法，但我想找到一种具有 100% 确定性而不是 99.9999999% 确定性的替代方案。

该算法花费的时间是 isProbicallyPrime(40) 的两倍，但根据我的基准测试，它比问题中的算法 10133,307 ± 448,365 ops/s 快得多 (50%) 14822,264 ± 639,563 ops/s。我还返回 n=1 的正确值，并通过使用位操作来提高 for 循环中偶数正值 ((num & 1) == 0) 和奇数 (i =我+奇数<< 1).

它更快的原因是，通过排除可被二和三整除的数字，我们只需要检查数字 6*k +-1 且 k = 1 ... sqrt(n) 是否为素数。

public static boolean PrimeTime(int num) {
  if(num < 4) {
    return num >= 2;
  }
  if((num & 1) == 0 || num % 3 == 0) {
    return false;
  }
  int max = (int) Math.sqrt(num);
  boolean[] notPrimes = new boolean[max];
  int lowestPrime = 5;
  if(lowestPrime * lowestPrime <= max) {
    int findMax = (int) Math.sqrt(notPrimes.length);
    for(int odd = lowestPrime; odd <= findMax; odd = odd + 2) {
      if(!notPrimes[odd - 1]) {
        for(int i = odd * odd - 1; i < notPrimes.length; i = i + odd << 1) {
          notPrimes[i] = true;
        }
      }
    }
  }
  for(int i = lowestPrime; i <= notPrimes.length; i = i + 6) {
    if(!notPrimes[i - 1]) {
      if(num % i == 0) {
        return false;
      }
    }
    if(i + 1 < notPrimes.length && !notPrimes[i + 1]) {
      if(num % (i + 2) == 0) {
        return false;
      }
    }
  }
  return true;
}