java - Java中的欧拉第10个解决方案

Question

我试图解决这个问题并编写代码，但它不起作用。我尝试使用断点，它似乎工作但它没有..我哪里出错了？

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

我的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

你的代码可以工作，只是需要很长时间。您可以采取更好的方法来找到素数；看一下Atkin ¹的筛子，这是一种通常用于查找小于某个整数的素数的算法。

---

¹ Atkin筛子是 Eratosthenes 筛子的优化版本。正如@DennisMeng 指出的那样，后者也应该足够快并且可能更容易编码。