欧拉项目＃10项目总和

Question

我正在欧拉项目＃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并找出有148933个素数低于2000000

它也需要你，例如，程序员可以为代码添加额外的检查，以确定数组访问没有超出数组的界限（除非您使用的语言为您执行此操作，例如Java或C＃）。还有一个原因是，它需要你添加代码来保存图书，即跟踪当前有多少个数组单元格被占用。

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

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

从一个简单的计划开始，并用不同的代码段来实现这些步骤。如果每段代码都有一个简单的，明确的责任，那么更容易保持最佳状态。如果你把所有的事情都弄得一团糟，事情会变得更加困难。例如，如果您存储了在矢量中找到的素数，那么这可以让您查看数字以查看是否一切正常，并且可能将它们与已知的素数列表（如The First 10,000 Primes或质数高达1,000,000,000,000在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 

显然，标准“如果没有公约数p在发现”您需要使用一个标志，像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，这对于欧拉任务中涉及的小数字来说已经足够了。通过引入合适的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 

如果ñ太大，形成sieve数组，你将需要细分阵列。如果您必须这样做，请参见here。还有一种算法，Legendre计算素数的方法的一种变体，它计算素数的总和，但它非常复杂。