euler项目问题10的错误答案

uqdfh47h 于 2021-07-08 发布在 Java

关注(0)|答案(1)|浏览(293)

**结束。**此问题需要详细的调试信息。它目前不接受答案。
**想改进这个问题吗？**更新问题，使其成为堆栈溢出的主题。

上个月关门了。
改进这个问题
我试图解决欧拉计划的第10个问题，这个问题要求所有素数之和低于200万（参考文献）。我得到的答案是 143042032116 ，但实际答案是 142913828922 . 代码有什么问题？

package projectEuler;

public class Euler10 {

    public static void main(String[] args) {
        // sum of prime numbers below 2million
        long sum=0;

        int maxValue=2*1000*1000;
        for(int i=0;i<maxValue;i++) {
            boolean isPrime=true;   

            for(int j=2;j*j<i;j++) {
                if(i%j==0) {
                    isPrime=false;
                }
            }
            if(i<2) {
                isPrime=false;
            }
            if(isPrime==true) {
                sum+=i;
            }
        }

        System.out.println(sum);        
    }      
}

Java

来源：https://stackoverflow.com/questions/64958568/wrong-answer-for-question-10-of-project-euler

1条答案

按热度按时间

kmbjn2e31#

问题似乎出在嵌套循环的情况下，应该 j * j <= i 排除奇数的平方。
此外，嵌套循环应优化为在检测到非素数时立即完成。
更新后的代码如下：

long sum = 0L;

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

    boolean isPrime = true;   

    for(int j = 2; isPrime && j*j <= i; j++) {
        if(i % j == 0) {
            isPrime=false;
        }
    }
    if(i < 2) {
        isPrime = false;
    }
    if(isPrime) {
        sum += i;
    }
}

System.out.println(sum);

它产生正确的响应：

142913828922

如果循环中不包含偶数，则剩余奇数素数的和可以更快地计数：

long sum = 2L; // add 2, as all the following even numbers are ignored

int maxValue = 2_000_000;
for (int i = 3; i < maxValue; i += 2) {

    boolean isPrime = true;   

    for(int j = 3; isPrime && j*j <= i; j += 2) {
        if(i % j == 0) {
            isPrime = false;
        }
    }
    if(isPrime) {
        sum += i;
    }
}

赞(0）回复(0）举报 2021-07-09

我来回答

euler项目问题10的错误答案

1条答案

相关问题

热门标签

最新问答