找到40億以下的所有素數的最快方法

我試圖在2 ** 32下打印每個素數。現在，我使用一個布爾向量來構建篩子，然後在篩子後打印出素數。只需要4分鐘即可打印出高達10億次的素數。有沒有更快的方法來做到這一點？這裏是我的代碼找到40億以下的所有素數的最快方法

#include <iostream> 
#include <cstdlib> 
#include <vector> 
#include <math.h> 

using namespace std; 

int main(int argc, char **argv){ 
    long long limit = atoll(argv[1]); 
    //cin >> limit; 
    long long sqrtlimit = sqrt(limit); 

    vector<bool> sieve(limit+1, false); 

    for(long long n = 4; n <= limit; n += 2) 
    sieve[n] = true; 

    for(long long n=3; n <= sqrtlimit; n = n+2){ 
    if(!sieve[n]){ 
     for(long long m = n*n; m<=limit; m=m+(2*n)) 
     sieve[m] = true; 
    } 
    } 

    long long last; 
    for(long long i=limit; i >= 0; i--){ 
    if(sieve[i] == false){ 
     last = i; 
     break; 
    } 
    } 
    cout << last << endl; 

    for(long long i=2;i<=limit;i++) 
    { 
    if(!sieve[i]) 
     if(i != last) 
     cout<<i<<","; 
     else 
     cout<<i; 
    } 
    cout<<endl;

來源

2013-09-21 ordinary

它應該花費超過4分鐘*打印*頭十億素數waaaaay。 – Mysticial

我想以最快的方式將跳過你知道黃金的arent所有的數字，例如，數字結尾用'2'，'4'，5''（5）後，'6'，'8'，'0 ' – enginefree

我同意@Mysticial它應該超過4分鐘（除非你有一臺超級計算機）。 – enginefree

這可能會加速它的有點：

#include <algorithm> 
#include <iostream> 
#include <iterator> 
#include <vector> 

int main() 
{ 
    std::vector<unsigned long long> numbers; 
    unsigned long long maximum = 4294967296; 
    for (unsigned long long i = 2; i <= maximum; ++i) 
    { 
     if (numbers.empty()) 
     { 
      numbers.push_back(i); 
      continue; 
     } 

     if (std::none_of(numbers.begin(), numbers.end(), [&](unsigned long long p) 
     { 
      return i % p == 0; 
     })) 
     { 
      numbers.push_back(i); 
     } 

    } 

    std::cout << "Primes: " << std::endl; 
    std::copy(numbers.begin(), numbers.end(), std::ostream_iterator<int>(std::cout, " ")); 

    return 0; 
}

這是一種埃拉托色尼的篩（倒數的，而不是限制下，每個編號開始和消除倍數，它從2開始並忽略倍數直到極限）。

來源

2013-09-21 02:22:41

這個代碼是否適合你？ – ordinary

是的。它編譯並運行（但超時）ideone。使用VS2010和VS2012編譯並運行它需要2分鐘左右的時間。 –

最快的方法可能是採取預生成列表。

http://www.bigprimes.net/有14億美元的素數可供下載，其中應包括每個低於300億左右的素數。

我想加載二進制文件可能需要很長時間，當它是幾千兆字節的大小。

來源

2013-09-21 02:49:14 Yakk

在線競賽網站通常只接受源代碼，並且有源代碼大小限制可以防止這種情況。 –

在定期處理素數的程序員中，普遍認爲生成素數比從磁盤讀取質數要快。 – user448810

你有沒有基準測試哪些花費最多時間？它是篩網本身，還是輸出的書寫？

一個快速的方法來加快篩是不用擔心所有的偶數。只有一個偶數是首要的，你可以對它進行硬編碼。如果你遇到物理內存的限制，這會將陣列的大小減半，這將極大地幫助你。

vector<bool> sieve((limit+1)/2, false); 
... 
    for(long long m = n*n/2; m<=limit/2; m=m+n) 
    sieve[m] = true;

至於輸出本身，cout是出了名低效的。這可能是更有效的調用itoa或某些等效自己，然後用cout.write以進行輸出。你甚至可以去舊學校，並使用stdout和fwrite。

來源

2013-09-21 05:07:38

我討論我的blog，在那裏我找到的第一個十億質數的和產生大量的素數的問題11138479445180240497.我描述了四種不同的方法：

蠻力，測試每個數從2開始使用試用部門。
生成使用具有強僞測試底座2，圖7和61a的2,3,5,7輪，然後測試素性候選人;這種方法只能達到2^32，這對我來說總計第一個十億個素數是不夠的，但對你來說就足夠了。
由於梅麗莎奧尼的算法，使用嵌入在一個優先級隊列，這是相當緩慢篩。
分段埃拉托色尼，這是非常快的，但需要空間來存儲篩分素數篩子本身的篩。

來源

2013-09-21 15:08:43 user448810

找到40億以下的所有素數的最快方法

回答

相關問題