總計低於200萬的素數

您可能聽說過一個名爲Project Euler（projecteuler.net）的網站。我正在研究第一個問題，這些問題很瑣碎，我正在討論標題中描述的問題。總計低於200萬的素數

這不是關於優化或任何事情 - 大約需要千分之九秒才能完成。它給了我錯誤的總數。

有人可以幫助我嗎？我不知道爲什麼我得到的答案 - 從數組總數（atotal）和總數（通常加起來的總數） - 是不正確的。他們都顯示的答案是947402457，它告訴我的網站是錯誤的答案。

如果這只是措辭，問題就在這裏：http://projecteuler.net/index.php?section=problems&id=10

什麼也是很奇怪的是，據我所知，當時，在年底的時候，你可以輸入該素數，你想查看（將其從數組中取出），它會給你正確的答案。

#include <cstring> 
#include <cstdlib> 
#include <iostream> 
#include <cmath> 
#include <ctime> 

typedef unsigned long int bignum; 
//there are 666671 primes below two million 
int main(){ 
    using namespace std; 
    bignum top = 2000000; 
    bignum total = 0; 
    bignum atotal = 0; 
    //hardcode 2 and 3 
    total += 5; 
    int inc = 2; 
    bignum n = 5; 
    double sq = n; 
    bignum np = 1; 
    bignum *pa = new bignum[top]; 
    pa[0] = 2; 
    pa[1] = 3; 
    while (n < top){ 
     int div = 5; 
     int divinc = 2; 
     int p = 1; 
     //check if number is prime 
     //check divisiblity from any possible prime up to the square root of n 
     //first hardcode 2 and 3 
     if(n%2==0||n%3==0) 
      p = 0; 
     else{ 
      while(div<=sqrt(sq)){ 
       if(n%div==0){ 
        p = 0; 
        break; 
       }else{ 
        div = div + divinc; 
        if(divinc==2) divinc = 4; else divinc = 2; 
       } 
      }if(p!=0){ //if it's a prime - 0 is not, 1 is prime 
       total = total + n; 
       np++; 
       pa[np] = n; 
       //cout << np << " prime number: " << n << endl; //takes too long if it prints everything 
      } 
     } 
     n += inc; 
     if(inc==2) inc = 4; else inc = 2; 
    } 
    for (int c=0;c<=np;c++){ 
     atotal += pa[c]; 
    } 
    cout << "Total " << top << ": " << total << endl; 
    cout << "Array total: " << atotal << endl; 
    cout << "Elapsed time: " << clock() << " " << CLOCKS_PER_SEC << "s of a second" << endl << endl; 
    while(true){ 
      int ptoview = 0; 
      cout << "Enter the number of the prime you would like to see (you can view every prime number below "<<top<<") "; 
      cin >> ptoview; 
      if (pa[ptoview-1]){ 
       if (pa[ptoview-1] < top) 
        cout << ptoview << " prime: " << pa[ptoview-1] << endl; 
       else 
        cout << "Too high/low" << endl; 
       cout << endl; 
      } 
     } 
    system("PAUSE"); 
    return 0; 
}

來源

2011-02-26 pighead10

@Pig Head：你的算法適用於少於2000000的數字嗎？我的意思是，10,15或20. – 2011-02-26 14:45:34

在你的代碼中，「//有666671個素數低於200萬」的陳述完全不正確。事實上，它高出大約4的因子。 – 2011-02-26 16:30:49

當我運行你的程序時，它說以下是素數：25,35,49,55,65，... – Blastfurnace 2011-02-26 17:41:48

這裏是至少一個線索的問題。看看會發生什麼，當你更換：

for (int c=0;c<=np;c++){ 
    atotal += pa[c]; 
}

有：

for (int c=0;c<=np;c++){ 
    bignum oldatotal = atotal; 
    atotal += pa[c]; 
    if (atotal < oldatotal) 
     cout << "Hmmm: " << oldatotal << " " << atotal << endl; 
}

我得到的是這樣的：

Hmmm: 4294819625 12858 
Hmmm: 4294864122 123849 
Hmmm: 4294717053 27802 
Hmmm: 4294697657 51420 
: : : 
Hmmm: 4293781002 792849 
Hmmm: 4294658253 1676602 
Hmmm: 4293686116 710941 
Hmmm: 4294706293 1737578 
Total 2000000: 947402457 
Array total: 947402457

我不會進入細節，因爲這是一個拼圖，我假設你想保持它至少有點挑戰性:-)

是的，你說得對（根據你的評論），所以我會讓答案不那麼鈍，所以對其他人更有用。

unsigned long類型不足以容納所有這些素數的總和，因此它正在環繞。

是否它可以容納實際的素數我沒有檢查過，但下一段的答案也會解決這個問題。

您可能想嘗試將bignum重新定義爲「更大」類型，如unsigned long long（如果可用）。

來源

2011-02-26 14:50:06 paxdiablo

這不公平！看起來typeof（oldtotal）是bignum – 2011-02-26 15:02:44

我完全不理解這個... – pighead10 2011-02-26 19:21:10

我查看了數據類型，並意識到數字已經接近「long int」的最大值 - 我將typedef更改爲「unsigned long長整型「，它工作得很好 - 謝謝！ – pighead10 2011-02-26 19:38:35

沒有看到一切，只是sq未在主while循環中修改。這看起來不正確。（順便說一下，我曾經使用過濾器篩選素數）。

來源

2011-02-26 14:46:09 AProgrammer

我打算去，但是我沒有看到任何一點，因爲這已經很快了。 – pighead10 2011-02-26 18:55:50

你說得對，sq沒有被修改，這是問題所在。那麼，一個問題。 – pighead10 2011-02-26 19:19:38

總計低於200萬的素數

回答

相關問題