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

Question

我正在练习过去的基础java考试的考试试卷,我发现很难做一个for循环工作来测试一个数字是否是素数.我不想通过为更大的数字添加效率测量来使其复杂化,这只是至少适用于2位数字的东西.

目前,即使n是素数,它总是返回false.

我认为我的问题是我在for循环本身出错了,在哪里放"return true".并且"返回虚假;"......我确信这是我犯的一个非常基本的错误......

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

我无法在stackoverflow上找到其他帮助的原因是因为类似的问题要求更复杂的实现以获得更有效的方法.

Answer 1

你的for循环有一点问题.它应该是: -

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

当然,你不想在n除以时检查余数n.它会永远给你1.

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

所以,你可以改变你的for循环: -

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

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