c# - Project Euler 10 : simple code is not giving the desired result, 需要帮助理解原因

Question

我正在解决 Project Euler 问题，目前我排名第 10。

首先:我知道还有其他解决方案，我目前正在使用埃拉托色尼筛法编写另一种方法。 我希望你能帮助我理解为什么这段代码不起作用。

这是我的代码(问题涉及找到小于 200 万的每个素数的总和)。素数检查方法似乎工作正常，但结果比应有的要少。

class Euler10
{
    public static void Main()
    {
        long sum = 0; // Was originally an int. Thanks Soner Gönül!
        for(int i = 1; i < 2000000; i++) 
        {
            if (CheckIfPrime(i) == true)
                sum += i;
        }
        System.Console.WriteLine(sum);
        System.Console.Read();
    }

    static bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;

        for (int i = 3; i*i < number; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }
}

我得到的数字是 1,308,111,344，比应有的数字低两个数量级。代码非常简单，我对这个错误感到困惑。

编辑: 求和很长解决了数字问题，谢谢大家!不过，现在我得到 143042032112 作为答案:CheckIfPrime() 中的 i*i 并不总是正确的。使用 sqrt() 函数并添加一个(以补偿 int 转换)给出正确的结果。这是正确的 CheckIfPrime() 函数:

 bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;
        int max = 1 + (int)System.Math.Sqrt(number);
        for (int i = 3; i < max; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }

编辑 2: Will Ness 帮助我进一步优化了代码(计算数字的平方根并将其与 i 进行比较比提升 i^2 然后将其与数字进行比较要慢):原始方法是它没有考虑数字是 i 的精确平方的边缘情况，因此有时返回 true 而不是 false。那么，CheckIfPrime() 的正确代码是:

bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;

        for (int i = 3; i*i <= number; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }

再次感谢大家!

Answer 1

您的代码不起作用，因为它尝试使用 32 位 int 来保存超过 32 位变量中最高值的数字。该题的答案是142,913,828,922，需要38位。

将 sum 的数据类型更改为 long 应该可以解决此问题。