0

因此，我开始学习编程并尝试使用 java 进行项目 euler。问题 10 看起来很简单，我想我可以使用以前在另一个问题中获取素数的方法。问题是，该方法有效，除非我将它放在 for 循环中，并且我无法看到这个和另一个之间的区别。

所以这是我的代码

package euler10;
public class Primesum {
    public static void main(String[] args) {
        int suma=0;

        for (int i=0; i<2000000; i=i+2){

            if (isPrime(i) == true){
                System.out.println(i);
                suma=suma+i;
            }

        }
        System.out.println(suma);
    }

    public static boolean isPrime(int num) {
         boolean prime = false;
         long i;
        for (i=2; i < Math.sqrt(num) ; i++){
            long n = num%i;
            if (n == 0){
                prime = false;
            } else {
                prime = true;
            }
        }
        return prime;
    }
}

isPrime 方法在循环之外工作得很好，但在其中它总是正确的。即使是偶数，它也会返回真，我认为这些不是很重要:)

4

2 回答 2

2

我真的不认为与循环有任何关系......

但是，代码中存在逻辑缺陷......

public static boolean isPrime(int num) {
    long i;
    for (i=2; i <= Math.sqrt(num) ; i++){
        long n = num%i;
        if (n == 0){
            return false;//found a divisor : not prime
        } 
    }
    //went through all the way to sqrt(num), and found no divisor: prime!
    return true;
}

只要找到第一个除数，我们就可以停下来，不需要找到所有的除数——那是另一种练习……

同样，从逻辑上讲，如果想以这种方式使用布尔变量，则在找到除数时，它会被初始化true，然后放入false，并保持在那个状态......

于 2013-08-14T15:11:07.203 回答
0

您的 isPrime 函数不正确；当您知道i的所有值不除num时，您应该将语句延迟return true到循环结束之后。

此外，试除法不是解决这个问题的好算法；使用筛子会快得多。这是一种使用埃拉托色尼筛法对小于n的素数求和的算法：

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            sum := sum + p
            for i from p*p to n step p
                sieve[i] := False
    return sum

这应该在不到一秒的时间内计算出少于 200 万的素数之和，这比您的程序快得多。如果你对素数编程感兴趣，或者如果你打算解决一些更高级的 Project Euler 问题并且你需要一些更快的算法，我在我的博客上谦虚地推荐这篇文章。

于 2013-08-14T15:29:17.283 回答