「お父さん、アルゴリズムってなぁに？」

16689 ワード
エラトステネスの篩 JavaScript プログラミング アルゴリズム JavaScript テキストリンク

※この記事は無職やめ太郎（@Yametaro）氏の「ワイ口調」記法をパクり...リスペクトしました。
※また、ネットミームを含みます。苦手な方は頑張って読んでください

前書き

8歳娘「なんか、学校のプログラミングの授業で中村君がアルゴリズムはいいぞとかいうけど、意味が分からない」

父「ほ～ん。で、中村君、何言ってたん？」

娘「なんかアルゴリズムを使ったら、めんどくさい計算がすぐにできる！とか、クソコードを撲滅できる！って言ってた」

父「ほ～ん、じゃアルゴリズムについて素数表示を例に教えるわ」

娘「わ〜い！」
ワイ「ワ〜イ！」
父「誰だこいつ」

分かりやすい例を出してみる～素数表示

父「娘ちゃん、素数ってわかるやろ？」

娘「うん、2,3,5...とかの1と自分自身以外に約数を持たない数でしょ」

父「そうそう。それじゃ、素数の条件ってわかるか？」

娘「えーと、偶数の素数は2のみであることと、、、」

ワイ「あとは、3以上では奇数であることやな」

父「（だからこいつ誰だよ）そうやな、じゃあ2~100までの素数をだしてみてみ」

娘「えーと、2,3,5,7,11...めんどくさいね！」

父「そうやろ、そのめんどくさい事をパッて解を出す手順のことをアルゴリズムというんや」

ワイ「そうだよ（便乗）」

父「...んで今回はエラトステネスの篩というアルゴリズムを使って素数を出していくで」

エラトステネスの篩を使用したコードを作ってみる

父「まず、最小値2と最大値100の変数と3つの配列を作っていくで」

let min = 2;
let max = 100;
let oddList = [];
let searchList = [];
let PrimeNimList = [];

娘「この配列たちってどういう意味？」

父「それは順次、解説していくで」

父「で、まず素数は2以外の奇数が必要条件のためminからmaxまでの奇数をoddListに格納したいんやけど」
父「娘ちゃんどう書く？」

娘「えーと」

  for(let i = min; max >= i; i++){
    if((( i % 2 ) != 0)){
      oddList.push(i);
    }
  }

父「そうやな！それで奇数を格納していくわけやな」

娘「oddListは奇数を格納する配列なんだね！」

父「そうや。でも、これだと素数である2が仲間外れになるから...」

  if (min <= 2){
    PrimeNimList.push(2);
  }

父「ここで、minが2以下の場合、後々素数として格納したいPrimeNimListに渡すんや」

娘「そうなんだね！」

ワイ「ちなみにここまでエラトステネスの篩の仕組みの理解を含めて、1.5時間かかりました」

父「何の話だよ」

父「...で、ここからがこのアルゴリズムのミソなんやけど」
父「１つ娘ちゃんにクイズをだすわ」
父「以下の手順をJSでコードを書いてみ」

  1,oddListの先頭の値の倍数を消去＝ふるいをかけてsearchListに値を渡す
  2,oddListの先頭の値をPrimeNimListに入れる
  3,oddListの中身を空にし、searchListに値渡しをしてもらう
  4,searchListを空にする
  5,oddListの先頭の値が、maxの平方根（変数stopNum）まで1~4を繰り返す

父「ちなみに変数stopNumはこれや」

let stopNum = Math.sqrt(max);

父「最大値100の平方根、ここではstopNum=10やな」

娘「うーん、まずoddListの先頭の値を定義して」
娘「その値の倍数を消去、残った数をsearchListに渡したいから...」

    let leadNum = (oddList[0])
    oddList.forEach(element => {
      if((element % leadNum) != 0){
        searchList.push(element)
      }
    });

娘「で、oddListの先頭の値をPrimeNimListに入れるのは...」

PrimeNimList.push(leadNum)

娘「次に、oddListの中身を空にし、searchListに値渡しをしてもらうから...」

    oddList = []
    oddList = searchList.slice(0, searchList.length)

娘「searchListを空にするならば...」

    searchList = []

娘「う～ん、最後の5番は繰り返すからどのfor文を使うのだろう...」

ワイ「ホワイルゥ...(小声)」

娘「while文か！で、条件分岐の指定するならば、、、」

  let n = 0;
  let stopNum = Math.sqrt(max);
  while (n < stopNum){
    let leadNum = (oddList[0])
    oddList.forEach(element => {
      if((element % leadNum) != 0){
        searchList.push(element)
      }
    });

    PrimeNimList.push(leadNum)
    oddList = []
    oddList = searchList.slice(0, searchList.length)
    searchList = []

    n = oddList[0]
  }

娘「できた！」

ワイ「やったぜ」

父「さすがワイの娘や！」
父「で、最後にループから抜けたら残りの奇数をPrimeNimListに入れるんや」

  oddList.forEach(element => {
    PrimeNimList.push(element)
  });

父「んで、これを関数にまとめてコンソール出力を付け加えた完成形やで」

SieveOfEratosthenes.js
let x = 2;
let y = 100

processing(x,y)

function processing (min,max) {
  let oddList = [];
  let searchList = [];
  let PrimeNimList = [];
  let stopNum = Math.sqrt(max);

  // 2は奇数の例外のため、min <= 2ならば2をPrimeNimListに入れておく
  if (min <= 2){
    PrimeNimList.push(2);
  }

  // 素数は2以外の奇数が必要条件のため
  // minからmaxまでの奇数をoddListに格納
  for(let i = min; max >= i; i++){
    if((( i % 2 ) != 0)){
      oddList.push(i);
    }
  }

  let n = 0;
  // oddListの先頭の値の倍数を消去＝篩をかけてsearchListに値を渡す
  // oddListの先頭の値をPrimeNimListに入れる
  // oddListの中身を空にし、searchListに値渡しをしてもらう
  // searchListを空にする
  // oddListの先頭の値が、maxの平方根（stopNum）まで繰り返す
  while (n < stopNum){
    let leadNum = (oddList[0])
    oddList.forEach(element => {
      if((element % leadNum) != 0){
        searchList.push(element)
      }
    });

    PrimeNimList.push(leadNum)
    oddList = []
    oddList = searchList.slice(0, searchList.length)
    searchList = []

    n = oddList[0]
  }

  // ループから抜けたら残りの奇数をPrimeNimListに入れる
  oddList.forEach(element => {
    PrimeNimList.push(element)
  });

  console.log(PrimeNimList);
  console.log(PrimeNimList.length);
}

父「このコンソールは、素数の配列（PrimeNimList）と素数配列の数（PrimeNimList.length）を表しているで」
父「んで、結果は...」

娘「できた！やったぁ！」

ワイ「くぅ～疲れましたw これにて完結です！それでは完走した感想（激うまギャグ）ですか...」

父「そういうのいいから」

結局アルゴリズムとは

父「このようにめんどくさい問題をいかに効率よく手順を踏んで解を出すことなんや」

娘「そうなんだ！じゃあ中村君がいってためんどくさい計算がすぐにできる！とか、クソコードを撲滅できる！って」

父「そうそう、無駄な変数などを書かずに済むわけや」

娘「わぁ、すごい！無駄なメモリリソースとかが省けるね！」

父「おお！そうや！娘ちゃんもきちんとPCメモリの仕組みも理解してるんやな！」

父「よ～し！今日は娘ちゃんが１つ賢くなったからご褒美にジョイ〇ルでも行くか！」

娘「わ～い！」
ワイ「ワ～イ！」
父「だから、お前誰だよ」
ワイ「あ、娘さんと仲良くしてる中村です」
父「（）」

おしまい