-1

n（ユーザー入力）未満のすべての素数を検出するプログラムをC++で作成するためのプログラミング割り当てがあります。課題の半分はエラトステネスのふるいに関係しています。私のコードは機能しています（読み取り：割り当てが完了しました）が、出力を編集する前は、 n-3、n-2、およびn-1が素数でなくても、無条件に素数として出力されていました。なぜこれが起こっているのかわかりません。プログラムがそのように機能している理由について、少しのフィードバックとアイデアをいただければ幸いです。変更されていないコードは次のとおりです。

ListNodeクラスとLinkedListクラスを使用していることに注意してください。どちらも完全に機能しています。編集：部分的なメインが追加されました。forループの2番目の項目がサイズ3であることに注意してください。サイズのままにしておくと、プログラムは3つの追加の非素数を出力します。

int main()
{
    for(int i = 0; i<my_list.size()-3; i++)
    {
        if(marked[i]==true)
            cout<<my_list[i]<<"\n";
    }
}

void eratosthenes(int item)
{
   bool run=true;
   int p=2, count=0;

   for(int i=2; i<=item; i++)
   {
      my_list.append(i);    // Entire list is filled with integers from 2 to n
      marked.append(true);  // Entire list is filled with true entries
   }

   while(run==true&&(2*p)<item)
   {
      count = 0;
      int i = (2*p);

      do {
         marked[i-2]=false;       // marked values are false and not prime
         i+=p;
      } while(i<item-2);

      for(int i=0; i<item-2; i++) // i starts at 0  and increments by 1 
      {                           // each time through the loop
         if(my_list[i]>p)
         {
            if(marked[i]==true)   // If a value stored in a node is true  
            {                     //   (prime), it becomes the new p.
               p=my_list[i];      //   The loop is then broken. 
               break;
            }
         }
      }
      for(int j=1; j<item-2; j++)
      {
         if(marked[j]==false)
         {
            count=1;
         }
      }
      if(count==0)
         run=false;
   }
4

3 に答える 3

1

完全な方法

    void Eratosthenes(int upperBound)
    {
        bool Prime[upperBound];
        for(int i = 0;i<upperBound;i++)
         Prime[i]=true;

        for (int i = 2; i <= sqrt(upperBound); i++) 
         {
             if (Prime[i]) 
             {
                for (int j = i * 2; j < upperBound; j += i) 
                    Prime[j] = false;

              }
         }
         for(int i=2;i<upperBound;i++)
         {
                 if(Prime[i]==true)
                 cout<<i<<" ";
          }
    }
于 2013-01-27T21:53:02.847 に答える
0

インデックス2から始めて、簡単にするためにブール値の配列を使用してみませんか。結果を出力するときに、値がtrueのインデックスを出力します。

于 2013-01-27T21:32:50.627 に答える
0

あなたのコードから：

  do{
     marked[i-2]=false;//marked values are false and not prime
     i+=p;
  }while(i<item-2);

このループは、私が理解しているようiに、素数の整数倍であるすべての数をp調べ、それらを素数ではないものとしてマークする役割を果たします。なぜあなたはその状態で止まるのi < item - 2ですか？とリストiのインデックスであればこれで問題ありませんが、この場合はそうではありません。素数ではなく、マークしている実際の数です。これが、素数としてマークされた制限（）に近い数値を取得している理由だと思います。ここでのループは、これらの数値に到達する前に終了します。my_listmarkeditemi

ちなみに、代わりにforループとしてこれを行うことができます。これは読みやすくなります。forループは、「セット内の各要素を通過する」という意味を持っているため（連続する整数、n番目ごとの整数、配列/リスト/両端キューなどの要素）、コードを読むプログラマーはすぐにそれを認識し、 whileループからそれを理解する必要はありません。

// mark every multiple of the current prime as not prime
for(int i = 2*p; i < item - 2; i += p)
{
    marked[i-2] = false;
}

（これは元のコードと同じですが、修正は適用されていません）。

アルゴリズム/コードを改善するためのいくつかの一般的なコメント：

よりわかりやすい変数名を使用してみてください。異なることを意味するために2回使用するiことは混乱を招きます。一般に、1文字は、変数が何を表すかについてはあまり意味がありません（ただしi、リスト/配列のインデックスであるforループなど、十分な場合もあります） 。 。

また、必要以上にリストをループしています。エラトステネスのアルゴリズムに必要な最小のふるいは、2つのネストされたforループです（リスト/配列をすべてに初期化することは含まれませんtrue）。

必要以上の作業を行っている例の1つはp、現在の場所を覚えてそこpから開始するのではなく、インデックス0からループして次に使用するものを見つけることです。my_list[i] > pその場合、最初はそれを超えていることがわかっているので、チェックする必要はありません。また、最後のループはbreak;早い段階で、プライム以外のループが見つかった後も続行しないようにすることができます（そして、そのポイントが何であるかはわかりません）。

Nikola Mitevの2番目の答えは、ふるいのより効率的で読みやすい実装です（ただし、正しく機能するように置き換える必要があります。理由は、ふるいの動作方法からかなり明確になっているはずsqrt(upperBound)upperBound/2upperBound/2です）。それについての説明。最初のループは「upperBoundまでのすべての数値を通過する」です。その中で、「現在の数が素数の場合、その素数のすべての倍数を調べて、それらを非素数とマークします」。そのinnerloopが実行された後、outer loopは続行され、次の番号を通過します。次の素数を見つけるために、最初から開始したり、別のforループを入力したりする必要はありません。

編集：sqrt(upperBound)正しいです。私はそれについて十分に注意深く考えていませんでした。

于 2013-01-27T22:33:16.997 に答える