0

首先：

boolean isPrime(int n) {
    if (n < 2)
        return false;
    return isPrime(n, 2);
}

private boolean isPrime(int n, int i) {
    if (i == n)
        return true;
    return (n % i == 0) ? false : isPrime(n, i + 1);
}

第二：

boolean isPrime(int n) {
    if (n < 0) n = -n;
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    return rec_isPrime(n, 3);
}

boolean rec_isPrime(int n, int div) {
    if (div * div > n) return true;
    if (n % div == 0) return false;
    return rec_isPrime(n, div + 2);
}

请解释为什么第二种解决方案比第一种更好。我在考试中提供了第一个解决方案，并且我的观点被认为是解决方案无效的说法。我想知道最大的不同是什么

4

2 回答 2

1

所以这是一个测试问题，我始终牢记一些教授拥有丰富多彩的特权，但我可以看到一些可能声称第一个较慢的原因：

  • 在计算素数时，您实际上只需要测试另一个素数是否是因子。第二个种子是奇数，3，然后添加 2 递归调用，跳过检查偶数因子并将所需的调用次数减少一半。

  • 正如@uselpa 指出的那样，第二个代码片段在测试因子的平方大于n 时停止。这实际上意味着在这个版本中，1 和 n 之间的所有奇数都已被考虑在内。这允许推断 n 是素数的速度比第一个在声明素数之前一直计数到 n 的速度更快。

  • 可能会争辩说，由于第一个测试是在递归函数内部而不是像第二个那样的外部方法，所以它是调用堆栈上的一个不必要的方法。

  • 我似乎也有人声称三元运算比 if-else 检查慢，因此您的教授可能会陷入这种信念。[就我个人而言，我不相信存在性能差异。]

希望这可以帮助。思考一些素数很有趣！

于 2016-03-03T10:18:30.550 回答
0

第一个解决方案的复杂度为 O(n)，因为它需要线性时间，第二个解决方案需要 O(sqrt(n)) 由于这行代码 : if (div * div > n) return true;，因为不需要寻找超过平方根的除数。有关这方面的更多详细信息，您可以查看：为什么我们要检查素数的平方根以确定它是否为素数？

于 2016-03-03T12:40:20.400 回答