에라토스테네스의 체(소수구하기) > feat.BOJ 1929

에라토스테네스의 체

: 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이라고 한다.

방법(ex.1~100 사이의 소수)

1. 위 표대로 1~100까지의 숫자를 쓴다.
2. 소수도 합성수도 아닌 유일한 자연수 1을 삭제한다.
3. 2를 제외한 2의 배수도 제거한다.
4. 3을 제외한 3의 배수도 제거한다.
5. 4의 배수는 2의 배수일 때 이미 지워져서 지우지 않아도 괜찮다. 대신 5의 배수를 제거한다.
6. 6은 지워져있음. 7의 배수를 제거한다.

   에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 어떤 수 m=abm=ab라면 aa와 bb 중 적어도 하나는 루트n 이하이다. 즉 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;
}