1

私は乱数の範囲を持っています。範囲は実際にはユーザーによって決定されますが、最大 1000 の整数になります。それらは次の場所に配置されます。

vector<int> n

値は次のように挿入されます。

srand(1);

for (i = 0; i < n; i++)
  v[i] = rand() % n;

すべての非素数の値を見つけるための別の関数を作成しています。これが私が今持っているものですが、シリーズでプライムとコンポジットの両方を取得するので、それが完全に間違っていることはわかっています.

void sieve(vector<int> v, int n)
{
  int i,j;

  for(i = 2; i <= n; i++)
     {
        cout << i << " % ";
        for(j = 0; j <= n; j++)
           {
              if(i % v[j] == 0)
                 cout << v[j] << endl;
           }
     }
}

この方法は通常、0 から 1000 までの一連の数字を持っていたときに機能しましたが、順番が狂って重複している場合は機能していないようです。ベクトルで非素数を見つけるためのより良い方法はありますか? 別のベクトルを作成し、n 個の数値で埋めて、その方法で非素数を見つけたくなるのですが、それは非効率的でしょうか?

範囲は 0 ～ 1000 であるため、0 ～ n を並べ替えてベクトルを作成し、ふるいを使用して素数を見つける方が簡単かどうか疑問に思っていますが、これは近づいていますか?

void sieve(vector<int> v, BST<int> t, int n)
{
  vector<int> v_nonPrime(n);
  int i,j;
  for(i = 2; i < n; i++)
      v_nonPrime[i] = i;

  for(i = 2; i < n; i++)
     {

        for(j = i + 1; j < n; j++)
           {
              if(v_nonPrime[i] % j == 0)
                 cout << v_nonPrime[i] << endl;
           }
     }
}
4

9 に答える 9

9

このコードでは:

if(i % v[j] == 0)
  cout << v[j] << endl;

インデックスをテストして、v[j] で割り切れるかどうかを確認しています。私はあなたがそれを逆にするつもりだったと思います、つまり：

if(v[j] % i == 0)

現在、i のランダムな約数を出力しています。素数ではないことがわかっている乱数を出力していません。また、出力に重複がありますが、おそらく問題ありません。

于 2008-10-29T21:26:29.790 に答える
4

まず、クヌースが最初に言ったと思います。時期尚早の最適化は多くのバグの原因です。最初に遅いバージョンを作成してから、それを速くする方法を見つけてください。

次に、外側のループの場合、実際にはnではなくsqrt（n）に移動するだけで済みます。

于 2008-10-29T21:15:08.440 に答える
2

基本的に、関係のない数がたくさんあるので、それぞれについて素数かどうかを確認する必要があります。

数値の範囲を事前に知っている場合は、その範囲（またはその平方根）で発生する可能性のあるすべての素数を生成し、生成された素数のいずれかによる除算性についてコンテナー内のすべての数値をテストできます。

素数の生成は、ErathostenesSieveによって行うのが最適です。そのアルゴリズムの多くの例が見つかります。

于 2008-10-29T21:14:58.673 に答える
1

プライムシーブを使用してみてください。ふるいを作成するための最大数（）を知る必要がありO(n)ます。次に、その範囲で（O(max_element) または問題の状態としてO(1000) == O(1)））素数のセットを作成し、各数が素数のセットに含まれるかどうかを確認できます。

于 2008-10-29T21:14:12.530 に答える
1

あなたのコードは単に間違っています。まず、i % v[j] == 0 をテストしています。これは逆方向であり、すべての数値を取得する理由も説明しています。第二に、（壊れた）割り切れるテストに失敗するたびに各入力数値をテストして出力しているため、出力には重複が含まれます。

その他の提案:

ベクトルの最大値とベクトルの要素数として n を使用することは、混乱を招き、無意味です。ベクトルの要素数を渡す必要はありません。ベクトルのサイズを照会するだけです。また、最大値をかなり迅速に把握できます (ただし、事前にわかっている場合は、それを渡すこともできます)。

上記のように、テストする必要があるのは sqrt(n) [ここで、n は vecotr の最大値] だけです。

上で提案したように、ふるいを使用して n までのすべての素数を生成し、それらの値を入力ベクトルから削除することもできます。特に素数をどこかに保存している場合、これはより迅速で理解しやすいかもしれません。

各数値を個別にテストする場合 (おそらく逆ふるいを使用)、各数値を順番に個別にテストすることをお勧めします。私見は、あなたが書いた方法よりも理解しやすいでしょう-kを増やし続けるために、k <nで割り切れるかどうか各数値をテストします。

于 2008-10-29T21:29:15.930 に答える
0

実装しようとするふるいの考え方は、素数（2）から始めて、その数の多数を消すという事実に依存します。したがって、素数「2」に依存するすべての数は事前に除外されます。

これは、すべての非素数を素数に分解できるためです。一方、素数は、1で除算するか、それ自体で除算しない限り、モジュロ0で除算できません。

したがって、このアルゴリズムに依存する場合は、アルゴリズムのこのプロパティを実際に復元するための何らかの手段が必要になります。

于 2008-10-29T21:15:47.330 に答える
0

ジェレミーは正しいです、基本的な問題はあなたのi % v[j]代わりにあなたですv[j] % i。

これを試して：

void sieve(vector<int> v, int n) {
  int i,j;

  for(j = 0; j <= n; j++) {
    cout << v[j] << ": ";

    for(i = 2; i < v[j]; i++) {
      if(v[j] % i == 0) {
        cout << "is divisible by " << i << endl;
        break;
      }
    }

    if (i == v[j]) {
      cout << "is prime." << endl;
    }
  }
}

v[j]の平方根までではなく、すべての数値で除算しようとしているため、最適ではありませんv[j]。そして、素数だけでなく、すべての数で除算しようとしています。

しかし、それは機能します。

于 2008-10-29T22:26:23.367 に答える
0

あなたのコードには多くの問題があるようです:

  1. 数値が素数か非素数かをテストしたい場合は、v[j] % i == 0 をチェックする必要があります。その逆ではありません。
  2. 数値がそれ自体で割り切れているかどうかを確認していません
  3. あなたは自分の番号を何度も何度もチェックし続けます。それは非常に非効率的です。

他の人が示唆したように、エラトステネスのふるいのようなことをする必要があります.

したがって、問題の疑似 C コードは次のようになります (コンパイラでこれをまだ実行していないため、構文エラーは無視してください。このコードは、アルゴリズムのみを説明するためのものです)。

vector<int> inputNumbers;

// First, find all the prime numbers from 1 to n
bool isPrime[n+1] = {true};
isPrime[0]= false;
isPrime[1]= false;
for (int i = 2; i <= sqrt(n); i++)
{
  if (!isPrime[i])
    continue;
  for (int j = 2; j <= n/i; j++)
    isPrime[i*j] = false;
}

// Check the input array for non-prime numbers
for (int i = 0; i < inputNumbers.size(); i++)
{
   int thisNumber = inputNumbers[i];
   // Vet the input to make sure we won't blow our isPrime array
   if ((0<= thisNumber) && (thisNumber <=n))
   {
      // Prints out non-prime numbers
      if (!isPrime[thisNumber])
         cout<< thisNumber;
   }
}
于 2008-10-29T21:40:27.733 に答える
0

最初に番号をソートするのが良いスタートかもしれません.nLogN時間でそれを行うことができます. それはあなたの他の問題への小さな追加です（私は思います）-数値が素数であるかどうかを見つけることです。
（実際には、そのような小さな数値セットを使用すると、ベクトル/セットのサイズのコピーを使用してソートをはるかに高速に実行し、ハッシュ/バケットソートなどを実行できます）

次に、セット内の最大数を見つけます（数値は無制限にすることができると思います-並べ替えまで上限がわからない-または最大値を見つけるために単一のパスを実行します）

次にふるいにかけます-他の人が言ったように

于 2008-10-29T21:43:00.880 に答える