欧拉项目编号10#

本文关键字：编号 项目 | 更新日期: 2023-09-27 18:32:45

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

我的回答是：

bool IsRishoni;
int soap = 0;
for (int i = 3; i < 2000000; i++)
{
    IsRishoni = true;
    for (int a = 2; (a <= Math.Sqrt(i)) && (IsRishoni); a++)
    {
        if (i % a == 0)
            IsRishoni = false;
    }
    if (IsRishoni)
    {
        soap = i + soap;
    }
}
Console.WriteLine(soap + 2);
Console.ReadLine();

为什么这不起作用？ 我得到的答案是1179908154...请帮忙。

欧拉项目编号10#

替换

soap = i + soap;

跟

soap = checked(i + soap);

..并且问题应该暴露出来。

这个问题有更多详细信息：C# 中的 int 没有溢出异常？

您的答案(存储在soap中(是一个大于int.Maxvalue(2,147,483,647(的值。

你的答案是 ~ 150,000,000,000

换句话说，您需要使用大于该数据类型的数据类型。 

long.MaxValue = 9,223,372,036,854,775,807
int.Maxvalue = 2,147,483,647

您所追求的结果可能太大，无法通过 32 位有符号整数 (int ( 表示。

让我们首先通过假设所有数字都是素数来确定结果的上限。通过求和，我们知道所有数的总和直到N(含(是N * (N + 1) / 2;因此，所有素数之和的上限为 2,000,000,000,000。这大于 int 允许的最大值 2,147,483,647，因此您可能会得到一个被静默忽略的数字溢出。

如果你想更准确地估计你的答案，你可以使用素数定理，它指出 0 到 N 之间的随机整数是素数的概率大约是 1 / ln(N) 。结合我们之前的公式，所有素数的近似和直到N是 N * (N + 1) / (2 * ln(N)) .对于 2,000,000，这估计约为 138,000,000,000，这仍然大于 int 的最大值。

要解决此问题，只需将用于 soap 变量的整型数据类型切换为 64 位整数表示形式，例如 long 。它的最大值是 9,223,372,036,854,775,807，因此它肯定能够代表您的数字。

long soap = 0;

另外一点：由于您使用的是素数序列，因此如果您将实现更改为埃拉托色尼筛，则可以获得巨大的性能提升(至少 100×(。

相关文章：