找到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亿以下的所有素数的最快方法

回答

相关问题