Java中的第10个解决方案

Question

我试图解决这个问题并编写代码，但没有成功。我用breakpoint试过了，它似乎有效，但没有。。我哪里做错了

第十个问题： 10以下的素数之和为2+3+5+7=17。 求200万以下所有素数之和

我的java代码：

 public class Problem_010 {

public static void main(String[] args) {

    long sum = 0;
    boolean control = false;

        for (int i = 3; i < 2000000; i+=2) {
            control = true;
            for (int j = 2; j < i; j++) {

                if ((i % j) == 0) {
                    control = false;
                    break;
                }
            }
            if (control == true) {
                sum = sum + i;                  
            }
        }

    System.out.println("Sum: " + (sum+2));
}

}

Answer 1

答案是正确的，如果你运行足够长的时间，它只是非常低效。试试这个

public static void main(String... ignored) {
    long sum = 2;
    for (int i = 3; i < 2000000; i += 2) {
        if (isPrime(i))
            sum += i;
    }

    System.out.println("Sum: " + sum );
}

private static boolean isPrime(int i) {
    for (int j = 3; j * j <= i; j += 2) {
        if (i % j == 0)
            return false;
    }
    return true;
}

Answer 2

你的代码会正常工作，只是需要很长时间。为了找到素数，你可以采取更好的方法；看看sieve of Atkin¹，这是一种常用于查找小于某个整数的素数的算法

---

¹阿特金筛是sieve of Eratosthenes的优化版本。正如@DennisMeng所指出的，后者应该足够快，并且可能更容易编码