2

可能重复：
用 java 编写 isPrime 的最优雅方式

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

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;
}
}
4

4 回答 4

4

除了对数字的处理之外1，该功能看起来还不错。可以进行的一项改进是利用所有大于 的素数3的形式为 的事实6k ± 1。

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

于 2012-12-16T20:45:12.303 回答
3

取决于你想得到多少花哨。

一个简单的改进是使用轮因式分解——而不是只尝试每个奇数（例如，不能被 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。您可以通过添加额外的素数来进一步改进它（维基百科文章中的轮子测试了 30 个中的 8 个），但代价是快速增加代码大小。

如果您不介意用一些严肃的数学来弄脏您的手，那么可以使用疯狂的数论方法，例如Miller-Rabin 测试。请注意，使用正确的证人集，这些方法可证明对合理范围内的所有数字都是正确的（请参阅“测试的确定性变体”）。

于 2012-12-16T20:48:11.030 回答
1 
BigInteger.valueOf(x).isProbablePrime(50)

假设您愿意容忍 1/1000000000000000 的错误机会，那可能会非常快。

于 2012-12-16T20:47:45.017 回答
0

看看 Eratosthenes 的筛子 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

于 2012-12-16T20:45:56.073 回答