検索Algorithm|小数

問題の説明

1から入力した数字nまでの小数を返す関数を作成します.
小数は1とそれ自体の数です.
(1は小数ではありません.)

せいげんじょうけん

nは2以上1000000以下の自然数である.

例

nresult10453

📍初めての試み

function solution(n){
  let primeNum = 0;
  for(let i=2; i<=n; i++){
    let zeroRemainder =0;
    for(let j=1; j<=i; j++){
      if(i%j===0){
        zeroRemainder++;
      }
    }
    if(zeroRemainder === 2){
      primeNum++;
    }
  }
  return primeNum;
}

数回の試みの後、googling、「エラトネスの体」の少数判別法によって、このアルゴリズムを開く方法を見つけた.

📍少数判別法

2から、素数を要求したい区間の全数をリストする.図中の灰色の矩形で囲まれた数はこれに相当する.

2は少数で、右に2と書きます.

自分以外の2の倍数をクリアします.

の残りの数の中で、3は少数なので、右側に3と書きます.(緑)

自分以外の3の倍数をクリアします.

の残りの数のうち、5は少数なので、右に5と書きます.(青)

自分以外の5の倍数をクリアします.

の残りの数の中で、7は少数なので、右側に7と書きます.(黄色)

自分以外の7の倍数をクリアします.

ビット目のプロセスを繰り返し、求めた区間のすべての少数の残りを返します.

エラトステネスのふるい->草点❗¥

下図のように、11^2>120は、11未満の倍数を削除するだけです.すなわち,120以下の数では,2,3,5,7の倍数を除いて残りは少数である.
nより小さい平方根の数の倍数だけ消去して解く.

参考資料|エラトスのふるい
参考資料|開発-プログラマーLv 1。小数点を検索

📍二次試行

function solution(n){
  let numbers = [];
  for(let i=0; i<=n; i++){
    numbers.push(i)
  }
  for(let j=2; j<=Math.sqrt(n); j++){
    for(let k=j; j*k<=n; k++){
      numbers[j*k] = 0;
    }
  }
  return numbers.filter(num => num !== 0).length-1 
  // 0과 1을 제외해야하지만 0은 filter에 의해 제외되므로 "1"을 전체 길이에서 제외하기 위해서 -1
}

プールが完了したら、数値配列をドアに変更する必要がなく、各インデックスに対応する数値を1つずつ入れる必要がありません.⬇

📍2回目の試み(検査)

function solution(n){
  let numbers = Array(n+1).fill(1); // 📍0~n 인덱스 까지 모두 1로 채움
  for(let j=2; j<=Math.sqrt(n); j++){
    for(let k=j; j*k<=n; k++){
      numbers[j*k] = 0;
    }
  }
  return numbers.filter(num => num !== 0).length-2
}

効率テストでは確かにもっとよくなりました.

📍 Setの別のプールの使用

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}

※from関数を使用

function solution(n) {
    
    let sosu = Array.from({length : n+1}, v => true);
    
    for(var num = 2; num<=Math.sqrt(n); num++){
        if(sosu[num]){
            for(var i=num*num; i<=n; i+=num){
                sosu[i] = false;
            }
        }
    }
    const result = sosu.filter(x => x == true);
    return result.length - 2 ;
}

- Array.from

Array.from()メソッドは、類似アレイオブジェクト(array-like object)または反復可能オブジェクト(iterable object)を浅くコピーすることによって、新しいArrayオブジェクトを作成します.
Array.from( arrayLike [, mapFn [, thisArg]])

パラメータ

arrayLike
アレイに変換する類似のアレイオブジェクトまたは重複可能なオブジェクト.

mapFn (Optional)
配列内のすべての要素に呼び出すマッピング関数.

thisArg (Optional)
mapfn実行時に使用する値.

戻り値
新しいArrayインスタンス.