0

我正在尝试打印 2**32 以下的每个素数。现在我正在使用布尔向量来构建一个筛子，然后在制作筛子后打印出素数。打印出多达 10 亿个素数需要 4 分钟。有没有更快的方法来做到这一点？这是我的代码

#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;
4

5 回答 5

4

我在博客中讨论了生成大量素数的问题，我发现前十亿素数的总和是 11138479445180240497。我描述了四种不同的方法：

  1. 蛮力，使用试除法从 2 开始测试每个数字。

  2. 使用 2、3、5、7 轮生成候选，然后使用强伪素测试对基数 2、7 和 61 进行素数测试；这种方法最多只能工作到 2^32，这对我来说不足以对前十亿个素数求和，但对你来说就足够了。

  3. 由于 Melissa O'Neill 使用嵌入优先级队列的筛子的算法，该算法非常慢。

  4. Eratosthenes 的分段筛，速度非常快，但需要空间来存储筛分素和筛子本身。

于 2013-09-21T15:08:43.463 回答
0

您是否对花费最多时间的内容进行了基准测试？是筛子本身，还是输出的写入？

加快筛子速度的一种快速方法是不再担心所有偶数。只有一个偶数是质数，您可以对其进行硬编码。这将您的阵列大小减半，如果您遇到物理内存的限制，这将非常有帮助。

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它来输出它。你甚至可以去老学校使用fwritewith stdout。

于 2013-09-21T05:07:38.100 回答
0

这可能会加快一点速度：

#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-21T02:22:41.347 回答
0

最快的方法可能是采用预先生成的列表。

http://www.bigprimes.net/有前 14 亿个质数可供下载，其中应该包括每个 300 亿左右的质数。

我想当它的大小只有几 GB 时，加载二进制文件可能需要很长时间。

于 2013-09-21T02:49:14.973 回答
0

我用 C 语言编写了一种快速方法，在我的 Ryzen 9 3900x 上使用单线程在三分钟内输出多达 40 亿个素数。如果你将它输出到一个文件，它最终是 2.298GB，我认为它使用大约 20GB 的内存来完成。

#include <stdlib.h>
#include <stdio.h>

#define ARRSIZE 4000000000
#define MAXCALC ARRSIZE/2

int main() {
    long int z;
    long int *arr = (long int*) malloc((ARRSIZE) * sizeof(long int));
    for (long int x=3;x <= MAXCALC; x++) {
        if (x % 10 == 3 || x % 10 == 7 || x % 10 == 9) {
            for (long int y=3; y < MAXCALC; y++){
                    z = x * y;
                    if (z < ARRSIZE)
                        arr[z] = 1;
                    else
                        break;
            }
        }
    }
    printf("2 3 5 ");
    for (long int x=7; x < ARRSIZE; x++) {
        if (x % 2 != 0 && x % 10 != 5)
            if (arr[x] != 1)
                printf("%ld ", x);
    }
    printf("\n");

    free(arr);
    return EXIT_SUCCESS;
}
于 2021-12-19T03:54:37.913 回答