0

我有下面的程序，我试图找到前 1000 个素数的总和。在代码中，解决方案 1 和 2 有什么区别？为什么我不应该将 count 变量放在 if 条件之外？如果我将变量放在 if 之外，我显然没有得到我需要的答案，但我不明白为什么它在逻辑上是错误的。这可能是一件简单的事情，但我无法弄清楚。请高手帮忙。

解决方案1：

public class SumOfPrimeNumbers {
public static void main(String[] args) {
    long result = 0;
    int number = 2;
    int count = 0;
    while (count < 1000) {
        if (checkPrime(number) == true) {
            result = result + number;
            count++;
        }
        number++;
    }
    System.out.println("The sum of first 1000 prime numbers is " + result);
}

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

}

解决方案2：

public class SumOfPrimeNumbers {    
public static void main(String[] args) {
    long result = 0;
    int number = 2;
    int count = 0;
    while (count < 1000) {
        if(checkPrime(number)==true)
        {
        result = result + number;                       
        }               
        count++; //The count variable here has been moved to outside the loop.
        number++;
    }       
    System.out.println("The sum of first 1000 prime numbers is "+ result);
}

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

}

4

3 回答 3

4

您不应该检查bool函数的返回值是否相等true：这一行

if(checkPrime(number)==true)

相当于

if(checkPrime(number))

最后，计数在if计数非素数和素数之外增加的解决方案，产生明显错误的结果。

以下是您应该考虑的“风格”几点：

  • checkPrime当候选除数大于数字的平方根时，可以停止签入候选除数
  • 如果您存储到目前为止所见的素数，并且仅通过素数列表中的数字检查可分性，您可以做得更好。当你在寻找前 1000 个素数时，这无关紧要，但对于更大的数字，这可能很重要。
于 2013-06-08T00:51:38.420 回答
3

增量的地方count非常重要。您的第一个代码块将前 1000 个素数相加，而第二个代码块将所有小于 1000 的素数相加。

于 2013-06-08T00:50:48.747 回答
1

在您的解决方案 2 中count，无论您的主要测试结果如何，每次循环都会递增。所以它不是计算素数，而是计算循环中的迭代。因此，您将检查 1,000 个连续的数字，而不是连续的素数（这涉及到超过 1,000 个数字的累积）。

除了其他人指出的之外，您可以通过以下方式更有效地检查素数：

public static boolean checkPrime(int number) {
    int s = Math.ceil(Math.sqrt(number));

    for (int i = 2; i <= s; i++) {
        if ((number % i) == 0) {
            return false;
        }
    }       
    return true;
}
于 2013-06-08T00:55:24.267 回答