エラトステネスの篩（ふるい）

エラトステネスの篩で知られている素数発見のアルゴリズムを実装してみた。

2行目以外は全てこれまでに説明したことの組み合わせのはず。たぶん。

var N = 100;  // ここでは100以下の素数を求める
var prm_arr = Array(N + 1).fill(1);  // 長さN+1で全ての要素が1となる配列を作る
for (var k = 2; k * k <= N; k++){
    for(var i = k; k * i <= N; i++){
        prm_arr[k * i] = 0;  // 配列のインデックスが合成数の要素を0に書き換える
    }
}
for (var j = 2; j <= N; j++){
    if(prm_arr[j] == 1) console.log(j);  // 配列の要素が1のインデックスは素数
}

2

3

5

7

11

13

17

19

23

29

31

37

41

43

47

53

59

61

67

71

73

79

83

89

97

こんなにシンプルに書けることにびっくり！！！