非常简单的素数测试 - 我认为我不理解for循环

loops for-loop iterator java primes

2022-09-03 16:22:49

我正在练习一个基本的java考试的过去的试卷，我发现很难让for循环用于测试一个数字是否是素数。我不想通过为较大的数字添加效率措施来使其复杂化，只是至少适用于2位数字。

目前，它总是返回 false，即使 n 是质数。

我认为我的问题是，for循环本身出了问题，以及在哪里放置“返回 true”和“返回 false”的位置。...我敢肯定，这是我犯的一个非常基本的错误......

public boolean isPrime(int n) {
    int i;
    for (i = 2; i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

我无法在其他地方找到关于stackoverflow的帮助的原因是，类似的问题要求更复杂的实现，以便有一种更有效的方法。

答案 1

您的循环有一个小问题。它应该是： -for

for (i = 2; i < n; i++)  // replace `i <= n` with `i < n`

当然，您不想在除以时检查余数。它将永远给你.nn1

实际上，您甚至可以通过将条件更改为： - 来减少迭代次数。因为不能除以大于的数字，除非我们考虑，我们根本不需要考虑。i <= n / 2nn / 2n

因此，您可以将循环更改为： -for

for (i = 2; i <= n / 2; i++)

答案 2

您可以更早地停止，并通过以下方式更快地跳过循环：

public boolean isPrime(long n) {
    // fast even test.
    if(n > 2 && (n & 1) == 0)
       return false;
    // only odd factors need to be tested up to n^0.5
    for(int i = 3; i * i <= n; i += 2)
        if (n % i == 0) 
            return false;
    return true;
}