欧拉计划 #10 素数总和 [英] Project Euler #10 Sum of Primes

问题描述

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

I am working on Project Euler's project #10 in which I am asked to find the sum of all primes below 2,000,000. For some reason, I cannot get my code to work. I am fairly certain I am not understanding which data types to use, but neither int, long, or long long seems to be working. Any help or advice would be greatly appreciated. Here is my code. Thanks.

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;
}

推荐答案

在学会走路之前不要尝试跑步.

Don't try to run before you have learnt the art of walking.

除非必须，否则不要使用像 int primes[100] 这样的固定大小的数组.

Don't use fixed size arrays like int primes[100] unless you have to.

一个原因是，这要求您，程序员，预先确定所需的大小 - 例如通过访问 第n个质数页面，发现2000000以下的质数有148933个.

One reason is that this requires you, the programmer, to determine the required size up front - for example by going to the nth Prime Page and finding out that there are 148933 primes below 2000000.

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

It also requires you, the programmer, to add additional checks to your code to ascertain that array accesses aren't exceeding the bounds of the array (unless you are using a language that does this for you, like Java or C#). Yet another reason is that it requires you to add code for book keeping, i.e. to track how many cells of the array are currently occupied.

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

Last but not least, allocating an array of 148933 integers as an automatic variable (i.e. on the stack) is likely to result in a crash because it blows the stack.

如果您使用 std::vector<>，那么所有这些麻烦都会立即消失，您的代码会变得更加简单.

If you use std::vector<> then all these headaches go away instantly, and your code becomes much simpler.

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

Start with a simple plan and implement the steps with separate pieces of code. It is easier to keep on top of things if every piece of code has a simple, well-defined responsibility. Things get more difficult if you entangle everything into one big bad clump.

例如，如果您将找到的素数存储在一个向量中，那么这允许您查看那里的数字以查看是否一切正常，并可能将它们与已知的素数列表进行比较(例如 前 10,000 个素数，或 primos.mat.br).你可以看，但你没必要看.如果您用输出代码散布所有内容，那么您总是必须查看所有内容.如果您只是将它们添加到总和中，那么除非您调试程序并按照每一步操作，否则您将看不到它们.

For example, if you store the primes you found in a vector then this allows you to look at the numbers there to see if all is well, and perhaps compare them to known lists of primes (like The First 10,000 Primes, or the primes up to 1,000,000,000,000 at primos.mat.br). You can look, but you don't have to. If you intersperse everything with output code then you always have to look at all of them. If you just add them to the sum then you cannot see them unless you debug your program and follow each and every step.

将您的计划制定为伪代码，以便您一目了然并完全理解它.如果没有计划，或者看不懂，那么结果很可能是cr*p.

Formulate your plan as pseudocode, so that you can take it in at a glance and understand it fully. If you don't have a plan, or if you don't understand it, then the result is very likely to be 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

显然，标准如果没有找到除数 p"要求您使用一个标志，例如 divisor_found，在内部循环之前被初始化为 false.因此进行了第一次改进:

Obviously, the criterion 'if no divisor p was found' requires you to use a flag, like divisor_found, that gets initialised to false before the inner loop. Hence the first refinement:

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

这可以毫不费力地实现.可以通过跳过一些不可能是素数的数字来改进候选者的枚举，例如 2 的倍数:

This can be implemented without further ado. The enumeration of the candidates can be improved by skipping some numbers that cannot possibly be prime, like multiples of two:

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

这会立即将您的工作量减半，这是 'wheel'.对于这样的问题，通过从 5 开始并以交替方式增加 2 和 4 来跳过 3 的倍数(mod 6 轮)是非常实用的.

This immediately cuts your workload in half, and it is the simplest example of a 'wheel'. For problems like this, it is very practical to skip multiples of 3 as well (mod 6 wheel) by starting with 5 and incrementing by 2 and 4 in an alternating fashion.

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 的倍数的扩展也相当简单.

Here, the trial division done in try does not need to consider 2 or 3 as potential divisors, because your method of enumerating candidates already excludes all their multiples. Extension to skipping multiples of 5 as well is fairly straightforward.

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

If you do an expensive calculation like sqrt(n) during each iteration of the innermost loop then your code gets slowed down to a crawl. n doesn't change during the lifetime of the inner loop, so compute the value once in the loop header instead of needlessly repeating the computation.

尽管如此，随机尝试不同的整数数据类型将一事无成.如果值不能变成负数 - 就像这里的情况 - 那么 unsigned 应该是你的第一选择.在当前系统上，这通常对应于 uint32_t，这对于 Euler 任务中涉及的琐碎小数来说已经足够了.你可以通过引入一个合适的 typedef 来为自己省去一些麻烦；这样你只需要更改一个应该出现的定义:

Be that as it may, randomly trying different integer datatypes will get you nowhere. If values cannot become negative - as is the case here - then unsigned should be your first choice. On current systems this usually corresponds to uint32_t, which is more than enough for the piddling small numbers involved in this Euler task. You can save yourself some hassle by introducing a suitable typedef; that way you only need to change one single definition should need arise:

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 的容量.

I've added a separate sum_t as well since a ballpark estimation of the sum puts it well beyond the capacity of a uint32_t.

在任何情况下，您都应该认真考虑在此处使用 埃拉托色尼筛网.它比轮式试验除法更简单，速度快几个数量级——即使是最简单的渲染也应该在几毫秒内解决这个欧拉任务.

In any case you should seriously consider using the Sieve of Eratosthenes here. It is simpler than wheeled trial division and several orders of magnitude faster - even the simplest rendering should solve this Euler task in a few milliseconds.

这篇关于欧拉计划 #10 素数总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！