3

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

首先：我知道还有其他解决方案，我目前正在使用 Eratosthenes 的筛子编写另一种方法。我需要您的帮助是了解为什么此代码不起作用。

这是我的代码（问题涉及找到 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，比它应该的低两个数量级。代码很简单，我对这个错误感到困惑。

编辑：使 sum 长期解决了数字问题，谢谢大家！不过，现在我得到 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： Ness 会帮助我进一步优化代码（计算数字的平方根并将其与 i 进行比较比提升 i^2 然后将其与数字进行比较要慢）：原始方法的问题在于它没有考虑到考虑其中 number 是 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;
    }

再次感谢人们！

4

5 回答 5

3

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

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

于 2013-05-28T10:25:15.080 回答
2

for (... i=3 ; i*i < number; i+=2 )是错的。它应该是

for (... i=3 ; i*i <= number; i+=2 )
 ...

两者都i必须number是同一类型的课程；这几乎不会给你溢出，因为你从 3 开始（除非number非常大，接近类型范围的上限）。

比较应该是包容性的，以捕捉number素数平方的情况。

于 2013-05-28T11:27:11.690 回答
2

您正在使用intforsum变量 which is32-bit但您尝试分配的变量多于Int32.Maximum which is 2,147,483,647。

但是你的结果是143,042,032,112需要更多的位而不是32存储它。

将其类型设置为long存储64 位。

long sum = 0;

这里有一个工作DEMO。

于 2013-05-28T10:27:29.307 回答
2

使用 long 应该会有所帮助。http://msdn.microsoft.com/en-us/library/ctetwysk.aspx 为您提供一个 64 位整数，其中 int 仅为 32 位。

于 2013-05-28T10:27:32.197 回答
1

你的算法不是埃拉托色尼筛法；模运算符给出了它。您的算法是奇数除法。这是一个使用埃拉托色尼筛法的函数：

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

CallingsumPrimes(2000000)给出了答案，出于对Project Euler的尊重，我不会写下来。该函数运行时间为 O( n log log n )，比原始程序的 O( n ^2) 好得多。有更好的筛分方法，但这很简单，也很容易做对，并且足以满足大多数目的，包括你的目的。您应该会在一秒钟内得到答案。

我将把它留给你用适当的数据类型翻译成 C#。

如果您对这个问题的更大版本感兴趣，我在我的博客中计算了前十亿素数的总和：11138479445180240497。

于 2013-05-28T13:10:20.777 回答