我做了这个素数函数.有没有更快或更好的方法

Question

可能的重复项：
最优雅的编写方式是Java中的Prime

。

我该如何使它更快或更好？我这样做是为了解决一个欧拉项目问题，然后对其进行了优化，但我确信这不是最好的方法

public static boolean prime(int number){
    int limit = (int) (1 + Math.sqrt(number) );
    if (number < 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;
    for(int i= 3; i < limit; i+=2)
        if(number % i == 0)
            return false;
    return true;
}
}

Answer 1

除了它对数字1的处理，这个函数看起来还不错。可以进行的一项改进是利用以下事实：所有大于 3 的素数都是 6k ± 1 的形式。

您可以选择更进一步，但您必须在提高性能与增加代码复杂性之间取得平衡。

Answer 2

取决于你想得到的花哨程度。

一个简单的改进是使用轮子分解 - 而不是只尝试每个奇数（例如，不能被2整除的数字），只尝试不能被几个小素数整除的数字。例如，下面是一个检查 2 或 3 可整除性的实现：

for (int i = 6; i < limit; i += 6) {
    if (number % (i + 1) == 0) return false;
    if (number % (i + 5) == 0) return false;
}

这只需要对每六个数字进行两次测试，而不是您的代码所做的 1/2。您可以通过添加额外的素数来进一步改进它（维基百科条目上的轮子测试 8 个中的 30 个），但代价是快速增加代码大小。

如果你不介意用一些严肃的数学来弄脏你的手，那么有一些疯狂的数论方法，比如米勒-拉宾测试。请注意，使用正确的见证集，这些方法对于合理范围内的所有数字都是可证明正确的（参见"检验的确定性变体"）。

Answer 3

BigInteger.valueOf(x).isProbablePrime(50)

这可能会很快，假设你愿意容忍 1/100000000000000000000 的错误几率。

Answer 4

看看埃拉托色尼的筛子http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes