1

この問題の目的は、2.000.000 番目の素数を取得し、2.000.000 番目の素数がどれであるかを判別できるようにすることです。

次のコードから始めます。

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

#define N 2000000

int p[N];

main(int na,char* arg[])
{
int i;
int pp,num;

printf("Number of primes to find: %d\n",N);

p[0] = 2;
p[1] = 3;
pp = 2;
num = 5;

while (pp < N)
{
  for (i=1; p[i]*p[i] <= num ;i++)
    if (num % p[i] == 0) break;
  if (p[i]*p[i] > num) p[pp++]=num;
  num += 2;
}

printf("The %d prime is: %d\n",N,p[N-1]);
exit(0);
}

ここで、プラグマ omp を介してこのプロセスをスレッド化するよう求められます。これは私がこれまでに行ったことです：

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

#define N 2000000
#define D 1415

int p[N];
main(int na,char* arg[])
{
int i,j;
int pp,num;

printf("Number of primes to find: %d\n",N);

p[0] = 2;
p[1] = 3;

pp = 2;
num = 5;

while (pp < D)
{
    for (i=1; p[i]*p[i] <= num ;i++)
        if (num % p[i] == 0) break;
    if (p[i]*p[i] > num) p[pp++]=num;
    num += 2;
}

int success = 0;
int t_num;
int temp_num = num;
int total = pp;

#pragma omp parallel num_threads(4) private(j, t_num, num, success)
{
    t_num = omp_get_thread_num();
    num = temp_num + t_num*2;

    #pragma omp for ordered schedule(static,4)
    for(pp=D; pp<N; pp++) {
        success = 0;
        while(success==0) {
            for (i=1; p[i]*p[i] <= num;i++) {
                if (num % p[i] == 0) break;
            }
            if (p[i]*p[i] > num) {
                p[pp] = num;
                success=1;
            }
            num+=8;
        }

    }
}

//sort(p, 0, N);

printf("El %d primer es: %d\n",N,p[N-1]);

exit(0);
}

ここで、私の「部分的な」解決策、つまり私の問題について説明しましょう。

最初の D 素数はシーケンシャル コードで取得されるため、大量の数の割り切れる可能性を確認できます。

各スレッドは素数の対角線を実行するため、スレッド間に依存関係がなく、同期の必要がありません。ただし、このアプローチには次の問題があります。

  1. あるスレッドが別のスレッドよりも多くの素数を生成する場合があります
  2. 問題 1. の直接的な結果として、N 個の素数が生成されますが、それらは順序付けられません。そのため、素数カウンター 'pp' が 'N' に達すると、最後の素数は 2.000.000 番目の素数ではなく、より高度なプライム。
  3. また、2.000.000 個の素数を生成するまでに、実際の 2.000.000 番目の素数に到達できるスレッドには、それを素数配列 'p' に配置するだけの十分な時間がない可能性もあります。

そして、質問/ジレンマは次のとおりです。

2.000.000 番目の素数がいつ生成されるかを知るにはどうすればよいですか?

ヒント: 10.000 候補の素数をバッチ処理するように言われました。その後、何かわからないことが起こったときに、10.000 の候補の最後のバッチに 2.000.000 番目の素数が含まれていることがわかり、クイックソートで並べ替えることができます。

これは本当に厳しいエクササイズであり、数日間ノンストップで試してみました.

4

2 に答える 2

2

必要な素数が 2000000 個だけの場合、最大 4.1MB のサイズの bitarray を 1 つ保持し、見つかった素数ごとにビットを反転できます。ソートは必要ありません。オッズのみの表現方式を実装して、bitarray のサイズを半分にします。

Sieve of Eratosthenesをセグメントで使用し、サイズは比例しsqrt(top_value_of_range)ます (または同様のもの - 目標は、各セグメントでほぼ同じ量の作業を実行することです)。n=2000000、n*(log n + log(log n)) == 34366806、およびprime[771]^2 == 34421689(0 ベース)については、最初の 771 個の奇素数を事前に計算します。

各ワーカーもビットを反転するときにカウントできるため、すべての範囲が終了したときに各範囲のカウントがわかり、2mln 番目の素数を含む 1 つの範囲をスキャンするだけで済みます。その素数を見つけます。または、各ワーカーにその範囲に従って独自の bitarray を保持させます。保持する必要があるのは 1 つだけで、残りは破棄できます。

エラトステネスのふるいを数える擬似コードは次のとおりです。

Input: an integer n > 1

Let A be an array of bool values, indexed by integers 3, 5, ... upto n,
initially all set to true.

count := floor( (n-1)/2 )
for i = 3, 5, 7, ..., while i^2 ≤ n:
  if A[i] is true:
    for j = i^2, i^2 + 2i, i^2 + 4i, ..., while j ≤ n:
      if A[j] is true:
        A[j]  := false
        count := count - 1

Now all 'i's such that A[i] is true are prime,
and 'count' is the total count of odd primes found.
于 2012-11-23T13:16:39.173 に答える
1

2つのアプローチが考えられます。

  1. 200 万番目の素数の候補が得られると、欠落している素数がなくなるまで、スレッドは候補よりも低い素数を計算し続けます。次に、素数のリストを並べ替えて、そこから 200 万分の 1 を取得できます。

  2. スレッドが連続した素数のブロックを生成している場合、スレッドはブロックを個別に維持する必要があり、その後、素数のブロックをマスター リストに再構築できます。再構築を行うスレッドは、200 万番目の素数が見つかると、プログラムを終了できます。

于 2012-11-22T21:48:38.770 に答える