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

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 億以下のすべての素数が含まれているはずです。

サイズが数ギガバイトの場合、バイナリのロードに時間がかかりすぎる可能性があると思います。

于 2013-09-21T02:49:14.973 に答える
0

最も時間がかかっているものをベンチマークしましたか? それはふるいそのものですか、それとも出力の書き込みですか？

ふるいを高速化する簡単な方法の 1 つは、すべての偶数について心配するのをやめることです。素数である偶数は 1 つだけで、それをハードコーディングできます。これにより、アレイのサイズが半分になり、物理メモリの制限にぶつかっている場合に非常に役立ちます。

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を出力するために使用する方が効率的かもしれません。古い学校に行っfwriteてstdout.

于 2013-09-21T05:07:38.100 に答える
0

Ryzen 9 3900x で単一のスレッドを使用して、3 分以内に最大 40 億の素数を出力する高速な方法を C で作成しました。ファイルに出力すると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 に答える