0

アルゴリズムの問題(こちら)に取り組んでいます。

与えられた引数以下のすべての素数の合計を返したいです。
例えば、

sumPrimes(10) //returns 17. (2,3,5,7の合計)
sumPrimes(20) //returns 77. (2,3,5,7,11,13,17,19の合計)
sumPrimes(977) //returns 73156.

下記の私の作ったコードでは、引数(26)までは正しい数を返すのですが、(27)以降おかしくなってしまいます。
((27)を素数として認識してしまうようです。)

以下が、私の作ったコードです。

function sumPrimes(num) {
  var arr = [];
  for(var a =2; a<=num; a++){
    arr.push(a);           //ここでまず2~numまでのすべての数字を配列に入れて
    }

  for(var i=0; i<=arr.length; i++){  //配列に入れた数字を順番にチェックしていく
    for(var d=2; d<arr[i]; d++){     //各数字を÷2、÷3、÷4..で割っていき、
       if(arr[i] % d == 0){        //割り切れる数に出会ったら、
       arr.splice(i, 1);            //その数字を配列から除く
      }
    }
  }
 return arr.reduce((sum,x) =>sum+x);    //最後に残った配列の数字を合計してreturn
}

どの部分が原因かおわかりでしょうか。
教えていただければ幸いです。
どうぞよろしくお願いいたします。

1 件の回答 1

2

致命的に問題なのはこの行です。

       arr.splice(i, 1);            //その数字を配列から除く

あなたのコードではfor(var i=0; i<=arr.length; i++)で配列全体を検査している(ついでに言うと「配列全体」ならi<arr.lengthですが、致命的でないことはあえて無視することにします)のですが、そのループの中でarrの中身を変更してしまっています。

例えば、i == 2の場合、arrの中身は、

2, 3, 4, 5, ...
      ^

ですから、本来4が素数かどうかチェックしているわけですが、d == 2の時に割り切れるので、配列の一部が削除され、

2, 3, 5, ...
      ^

と言う状態になります。

あなたの記述したループでは、i == 2のままd == 3から割り切れるかどうかのチェックを行うので、配列の中身の5と言う数字は2で割り切れるかどうかのチェックを受けていないことになります。

つまりあなたのコードは、直前の数字がどの数で割り切れると判断されたのかによって、素数判定の結果が変わってしまうことになります。5の場合はたまたまそれでも「素数である」と言う判定になりますが、他の数字の並びの場合に正しい結果になるのかどうかは予測困難です。1ステップずつ丹念に解析すれば、なぜ27が正しく素数と判定されないのかが分かるでしょうが、そもそも

配列をスキャンするループ内で要素の位置が変わるような操作はしない

ことを心がけた方が良いでしょう。

今回の課題の場合、最終的には合計を求めれば良いので、0arr中に存在しても結果には影響を与えませんから、先ほどの行を

       arr[i] = 0;            //その数字を配列から除く

と変更すれば、素数ではなかったと言うことを記録できることになります。


他にも、「どれか一つの数字で割り切れたらもう素数でないことは確定」⇒「そこで内側のループを中断しても良い」など、改良できる点はいろいろありますが、上記の修正だけで正しい結果が得られるはずです。試してみてください。

3
  • ご説明ありがとうございます。2つ質問があります。 1.内側のループついて改善したいのですが、ifの後に else{ // do nothing } を追加するという方法は、改良として良い方法でしょうか?  2.改良できる点がいろいろあるということなのですが、自分で何度見ても見つけられないので教えていただければ嬉しいです。
    – Suzuran
    Commented 2020年8月6日 13:40
  • @Suzuran さん、コメントありがとうございます。>1. 「else{ // do nothing }を追加する」については、何のメリットがあるのかがよくわかりません。コードが長くなるだけで無意味に思えます。>2. 「いろいろ」については、「どれか一つの数字で割り切れたら、そこで内側のループを中断」であったり、「割り切れるかどうかのチェックを√nで打ち切る」であったり、「素数じゃないとわかっている数字については割り切れるかどうかのチェックを省略」したり、あるいは「エラトステネスのふるい」を使ってループの構造自体を書き換えるなんてのが考えつくところです。今回のように調べたい範囲の数を表す配列を用意できる場合、前3つの改良を全部組み込んでやたらややこしいコードにするより、「エラトステネスのふるい」をシンプルに実装した方が簡潔で速くなるので、まずは「エラトステネスのふるい」がどんなものか調べてみられるのが良いかもしれません。
    – OOPer
    Commented 2020年8月6日 14:07
  • 詳しくご指摘いただきありがとうございます。調べて実装してみます。ありがとうございました^^
    – Suzuran
    Commented 2020年8月7日 8:29

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。