•  05-07-2019
  •  | 
  •  

質問

乱数の範囲があります。範囲は実際にはユーザーによって決定されますが、最大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;
           }
     }
}
役に立ちましたか？

解決

このコードでは：

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

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

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

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

他のヒント

まず、Knuthが最初に言ったと思います。時期尚早な最適化は多くのバグの原因です。最初に低速バージョンを作成し、次に高速バージョンを作成する方法を見つけます。

次に、外側のループでは、nではなくsqrt（n）に移動するだけです。

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

事前に数値の範囲がわかっている場合、その範囲（またはそのsqrt）で発生する可能性のあるすべての素数を生成し、分割可能性についてコンテナ内のすべての数値をテストできます。生成された素数のいずれか。

素数の生成はErathostenes Sieveが最適です。そのアルゴリズムの多くの例があります。

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

あなたのコードは単純に間違っています。最初に、i％v [j] == 0をテストしています。これは逆向きであり、すべての数値を取得する理由も説明しています。次に、（壊れた）分割性テストに失敗するたびに各入力番号をテストおよび出力しているため、出力には重複が含まれます。

その他の提案：

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

上記のように、sqrt（n）[nはvecotrの最大値]でテストする必要があります

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

各番号を個別にテストする場合（使用、推測、および逆ふるい）、各番号を順番に個別にテストすることをお勧めします。私見では、あなたがそれを書いた方法よりも理解しやすいでしょう-k <！> lt; nは常にkを増やします。

実装しようとするふるいのアイデアは、素数（2）から開始し、その数の多数を消すという事実に依存します。したがって、素数に依存するすべての数は<！> quot; 2 <！ > quot;事前に除外されます。

これは、すべての非素数を素数に分解できるためです。一方、素数は、1またはそれ自体で除算しない限り、モジュロ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;
   }
}

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

次に、セット内の最大の番号を見つけます（番号は無制限であると仮定します-ソートまで上限がわからない-または最大値を見つけるために単一のパスを実行します）

その後、ふるいに行く-他の人が言ったように

ジェレミーは正しい、基本的な問題は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]の平方根までではなく、<=>未満のすべての数で除算しようとするため、最適ではありません。そして、素数だけではなく、すべての数で分割しようとしています。

ただし、動作します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top