素数を数える

はじめまして、Sと申します。以後お見知り置きを。

初めてGESブログに記事投下させて頂きますので、分かり難い部分とかあったらごめんなさい。

私の記事の方向性は殆どが「誰得・気まぐれ」ですので息抜き程度に読んでいただけると幸いです。

 

今回取り上げるのは”素数を表示する”アルゴリズムです。

 

 

事前知識として、皆さんは素数がどのような数値か知っていますか？
簡単に説明しますと、「１とその数値以外では割り切れる正の整数値が存在しない正の整数」です。

例えば７が素数かどうかを知りたい場合、２～６の数字で割っていき、全てで割り切れなかったら、７は素数となります。

ではそれをC言語のプログラムで表現してみましょう。
範囲は１～１００で出しています。
-------------------------------------------------
int i;
for(i = 1; i < 100; i++){

int judge = 0; /*0:素数　1:素数ではない*/

int j;
/*調べたい数値より小さい値でループ*/
for(j = 1; j < i; j++){
  if( i % j == 0){
   /*割り切れたら素数じゃないからループを抜ける*/
   judge = 1;
   break;
  }
}

/*素数判定*/
if( judge == 0){
  printf("%d"は素数\n, i);
}
}
-------------------------------------------------

簡単に書くとこんな感じですね。

上記の例は試し割りと呼ばれるアルゴリズムです。
これも正しいアプローチなのですが、上記のコードですといくつか無駄な計算があります。
ですので個人的に計算の無駄を省いてみたコードを考えてみました。
割り算回数を減らすことに意識をしたのでその他の部分は最適化していません。
ソースが難しくて解らないって場合は是非ラボⅠに来て下さい！
先輩たちはみんなからの質問を待っています！


皆さんがこれからゲームを制作していくにあたって「これってどうやったら出来るんだろう」とか「他にも方法無いかなぁ」とか考えるときに、全く別な経験からアイディアが出ることがあります。
このソースを思いついたのも高校の数学の授業での知識が有ったからでした。
解決の種が何処に潜んでいるのかはわかりません。
なので余裕のある時に苦手なことでも好きな事でも、とにかく色んなことにチャレンジしてみて下さい。


-----------------------------------------------------------------------
#include <Windows.h>
#include <iostream>
#include <vector>


//最短手順で素数を数えるアルゴリズムテスト

int main(void){

int limit(1);

std::cout << "自然数を入力してね☆　" << std::endl;
std::cin >> limit;

if( limit < 2 ){
  std::cout << "値にエラーがありますので終了します" << std::endl;
  return 0;
}


//素数を格納する配列
std::vector<int> prime_number;

//最初に２を格納する
prime_number.push_back(2);

//今回はとりあえず１～１００までの素数を数える
for(int i(3); i < limit; i += 2){

  //最後を指すイテレータと、操作用イテレータを用意
  std::vector<int>::iterator it(prime_number.begin() );
  std::vector<int>::const_iterator endit(prime_number.end() );

  //現在配列に格納されている素数リストで割り算を行なって結果を見る
  for( ; endit != it; ){

   //割り算で割り切れない場合は次の要素を試す
   if( i % (*it) != 0){
    it++;
    continue;
   }
   //割り切れたらループを抜ける
   break;
  }
 
  //ループを抜けた時点でイテレータの値を比較する

  //操作用イテレータの値が　最後を指すイテレータを指している→ループ完走→素数として追加
  //同一の値になっていない→ループを途中で抜けた→素数ではない
  if( endit == it){
   prime_number.push_back(i);
  }
}


/*結果表示*/
//最後を指すイテレータと、操作用イテレータを用意
std::vector<int>::iterator it(prime_number.begin() );
std::vector<int>::const_iterator endit(prime_number.end() );

for( ; endit != it; it++){
  std::cout << (*it) << std::endl;
}


//終了メッセージ
std::cout << "エスケープキーを押してね" << std::endl;

while(1){
  if(GetAsyncKeyState(VK_ESCAPE) ){
   break;
  }
}

return 0;
}
-----------------------------------------------------------------------