歐拉項目＃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計算素數的方法的一種變體，它計算素數的總和，但它非常複雜。