欧拉计划 #10 素数总和

Question

我正在处理 Project Euler 的项目 #10，其中我被要求找出所有小于 2,000,000 的素数之和。出于某种原因，我无法让我的代码工作。我很确定我不了解要使用的数据类型，但 int、long 或 long long 似乎都不起作用。任何帮助或建议将不胜感激。这是我的代码。谢谢

int main(int argc, char *argv[])
{
int primes[100] = {2, 3, 5, 7};
//array of primes that have been found
int fillcell = 4;
//cell we are looking to fill
int testnum = 8;
//number being tested to see if it's a prime
int divprime;
int sum = 17;
for(testnum = 8, fillcell = 4 ; testnum < 2000000 ; ++fillcell)
{
    std::cout << "fillcell " << fillcell << std::endl;
    for( ; primes[fillcell] == 0 ; ++testnum)
    {
        std::cout << "testnum " << testnum << std::endl;
        for(divprime = 0 ; testnum % primes[divprime] != 0 ; ++divprime)
        {
            std::cout << "divprime " << divprime << std::endl;
            if(primes[divprime] >= sqrt(testnum))
            {
                primes[fillcell] = testnum;
                sum = sum + testnum;
                std::cout << "prime found " << testnum << std::endl;
                break;
            }
        }
    }
}
std::cout << "sum" << sum << std::endl;
}

Answer 1

在学会走路之前，不要尝试运行。

除非万不得已，否则不要使用 int primes[100] 等固定大小的数组。

一个原因是这需要你，程序员，预先确定所需的大小 - 例如通过转到 nth Prime Page 并发现在 2000000 以下有 148933 个素数。

它还要求您，程序员，向您的代码添加额外的检查以确定数组访问没有超出数组的边界（除非您使用的语言可以为您执行此操作，例如 Java 或 C#）。另一个原因是它需要您添加用于簿记的代码，即跟踪数组中当前有多少个单元格被占用。

最后但并非最不重要的一点是，将 148933 个整数的数组分配为自动变量（即在堆栈上）可能会导致崩溃，因为它会破坏堆栈。

如果您使用 std::vector<> 那么所有这些令人头疼的问题都会立即消失，您的代码也会变得更加简单。

从一个简单的计划开始，然后用单独的代码片段实施这些步骤。如果每一段代码都有一个简单的、定义明确的职责，就更容易掌控一切。如果你把所有东西都纠缠成一个大坏块，事情就会变得更加困难。

例如，如果您将找到的素数存储在一个向量中，那么您可以查看其中的数字以查看是否一切正常，并且可能将它们与已知的素数列表进行比较（例如 The First 10,000 Primes, or the primes up to 1,000,000,000,000 at primos.mat.br).你可以看，但没必要。如果您将输出代码穿插在所有内容中，那么您总是必须查看所有这些内容。如果您只是将它们加到总和中，那么您将看不到它们，除非您调试程序并遵循每一步。

把你的计划写成伪代码，让你一目了然，理解透彻。如果你没有计划，或者你不理解，那么结果很可能是cr*p。

for each candidate n between 2 and 2000000
    for each known prime p up to sqrt(n)
        if p divides n
            break
    if no divisor p was found // must be a new prime
        add n to the list of found primes

显然，标准 'if no divisor p was found' 要求您使用一个标志，如 divisor_found，在内循环之前初始化为 false。因此第一次细化：

for each candidate n between 2 and 2000000
    divisor_found := false
    for each known prime p up to sqrt(n)
        if p divides n
            divisor_found := true
            break
    if not divisor_found // must be a new prime
        add n to the list of found primes

这个不用多说就可以实现了。可以通过跳过一些不可能是质数的数字来改进候选人的枚举，例如二的倍数：

add 2 to the list of found primes
for each odd number between 3 and 2000000
    ...

这会立即将您的工作量减少一半，并且它是 'wheel' 中最简单的示例。对于这样的问题，跳过 3 的倍数（mod 6 轮）也非常实用，方法是从 5 开始，然后以交替方式递增 2 和 4。

add 2 and 3 to the list of found primes
for n = 5 to 2000000 step 6  // 6 = 2 * 3
    try n
    try n + 2

这里，try中的试分不需要考虑2或3作为潜在的约数，因为你枚举候选人的方法已经排除了他们所有的倍数。跳过 5 的倍数的扩展也相当简单。

如果您在最内层循环的每次迭代期间都进行了像 sqrt(n) 这样的昂贵计算，那么您的代码会变得缓慢得像爬行一样。 n 在内部循环的生命周期内不会改变，因此在循环头中计算一次值而不是不必要地重复计算。

尽管如此，随机尝试不同的整数数据类型会让您一事无成。如果值不能变成负数——就像这里的情况——那么 unsigned 应该是你的第一选择。在当前系统上，这通常对应于 uint32_t，这对于参与此 Euler 任务的小数来说绰绰有余。您可以通过引入合适的 typedef 来省去一些麻烦；这样你只需要改变一个定义应该出现：

typedef std::uint32_t num_t;
typedef std::uint64_t sum_t;
num_t const N = 2000000;
...

std::vector<num_t> primes;
...

for (num_t n = 3; n <= N; n += 2)
   ...

sum_t sum = 0;
for (num_t p: primes)
   sum += p;

我还添加了一个单独的 sum_t，因为对总和的粗略估计远远超出了 uint32_t 的容量。

无论如何你应该认真考虑在这里使用Sieve of Eratosthenes。它比轮式试验除法更简单，而且速度快几个数量级——即使是最简单的渲染也应该在几毫秒内解决这个欧拉任务。

Answer 2

DarthGizka 给了您一些很好的建议，包括更改您的算法以使用埃拉托色尼筛法。这是我的解决方案，我将留给您用您选择的语言重写：

function sumPrimes(n) # sum of primes <= 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

如果n太大无法组成sieve数组，则需要对数组进行分段。如果您必须这样做，请参阅 here。还有一种算法，勒让德数素数法的变种，计算素数之和，但是很复杂

欧拉计划 #10 素数总和

Project Euler #10 Sum of Primes

primes