エラトステネスの体(少数を得る)>feat.BOJ 1929

エラトステネスのふるい

:古代ギリシャの数学者は、ラ菌から発生した小数を探す方法で、任意の自然数nに対して、以下の小数の最も簡単で、最も速い方法を探していると考えています.

メソッド(ex.1-100間の小数)

の上の表に従って1から100の数字を書きます.

削除

は、少数でも合成数でもない唯一の自然数1である.

2に加えて、2の倍数も除去されます.

3に加えて、3の倍数も除去されます.

4の倍数は2の倍数で消去されており、消去する必要はありません.代わりに5の倍数を取り除く.

6がクリアされました.7の倍数を抜きます.
エラトネスのふるいで1~nの小数を知るためには,すべての倍数をnに分ける必要はない.数m=abm=abの場合、aaおよびbbの少なくとも1つはrootn以下である.すなわち、n未満の合成数mは、根nより小さい数の倍数を調べるだけで全てクリアできるので、根n以下の数の倍数をクリアするだけでよい.1人から100人以上の場合、事実上7の倍数に残っている49(77)、77(711)、91(7*13)が終わります.表の数字が112(121)より大きい場合は、11のほかに11の倍数を削除する必要があります.この過程で、最初に削除された数字は121(112)です.しかし、これは所定の範囲を超えた数字です.

BOJアルゴリズム問題1929

const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    :`3 16`).trim().split(' ');

// let fs = require('fs');
// let stdin = fs.readFileSync('/dev/stdin').toString().trim().split(' ');

let start = Number(stdin[0])
let end = Number(stdin[1])

let nums = new Array(end+1).fill(true);
//0과 1은 소수가 될 수 없다.
nums[0]=false;
nums[1]=false;

//에라토스테네스의 체
for (let i=2; i*i<=end; i++) {
    if(nums[i]) {
        for (let j=i*i;j<=end;j+=i) {
            nums[j]=false;
        }
    }
}

for (let i=start;i<=end;i++) {
    nums[i] === true ? console.log(i) : null;
}