[백준] 소수구하기

문제 읽자마자 이렇게 쉬운거 풀어도 되는건가 싶었다.

function solution(M, N) {
    let result = 0;
    for (let i = M; i <= N; i++) {
      if(i% 2 !== 0) {
        console.log(i)
      }
    }

    return result;
}

solution(3,    16)

여윾시나 정답을 보며 풀이를 이어나가보자

이문제는 에라토스테네스의 체 라는 방법을 사용해서 풀어야 한다고한다.
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이라고 한다.

https://www.youtube.com/watch?v=5ypkoEgFdH8

소수를 구할때 특징이 있다고 하는데
해당 수의 약수가 대칭된다고 한다.

0, 1, 2,는 제외 하고

3은 1과 3뿐이니 소수

4= 1, 2 ,4

5= 1, 5

6= 1, 2, 3, 6

7= 1, 7
...

이걸 봐도 코드로 어떻게 풀어가야할지 모르겠다.

에라토스테네스의 체 방법은 구해야 하는 최대수까지 나열 한다음 0, 1 제외하고 각 숫자의 배수들을 지워나간다.
이미 지워진 숫자는 넘어가며 최종적으로 남은 숫자를 반환하는데 그게 소수가 된다.

정답풀이 블로그
https://leylaoriduck.tistory.com/498

let fs = require('fs');
let inputs = fs.readFileSync('/dev/stdin').toString().split(' ');
let a = Number(inputs[0]);
let b = Number(inputs[1]);
let arr =[];
let answer = '';
for(let i=0; i<=b; i++){  // 입출력 예제 숫자 나열하기 
    arr.push(true);     // 0 ~ 16까지 
}
arr[0] = false;  //0과 1은 제외
arr[1] = false;


//에라토스테네스의 체 
for(let m=2; m<=b; m++){  
    if(arr[m]){
        for(let n=2; n<=b/m; n++){
            arr[m*n] = false;
        }
    }
}
for(let j=a; j<=b; j++){
    if(arr[j]) answer += j + '\n';
}
console.log(answer.trim())

https://pannchat.tistory.com/entry/%EB%B0%B1%EC%A4%80-1929-nodejs-%EC%86%8C%EC%88%98%EA%B5%AC%ED%95%98%EA%B8%B0
이분은 제곱근까지 나눈방법과 에라토스테네스의 체를 사용한 2가지방법 풀이