[자바스크립트(JavaScript)] 특정 범위에서 소수 구하기(에라토스테네스의 체)

해당 수가 소수인지 아닌지 반복문을 돌려서 구할 수도 있지만, 효율성이 많이 떨어진다.

특히 특정 범위에서 소수를 모두 구해야 하는 경우는 해당 범위 * 범위에 속한 수의 크기만큼 반복문을 돌려야하기 때문에 매우 비효율적이다.

function isPrime(number) {
    if(number === 1) return false;
    for(let i = 2; i < number; i++) {
        if(Math.floor(number/i) === number/i) return false;
    }
    return true;
}

function solution(n) {
    let answer = 0;
    for(let i = 1; i <= n; i++) {
        if(isPrime(i)) answer++;
    }
    return answer;
}

- 좋지 않은 예시

---

효율적으로 특정 범위에 있는 모든 소수를 구할 때 사용되는 알고리즘이 바로 에라토스테네스의 체이다.

에라토스테네스의 체는, 소수의 배수들을 차례대로 지워나가면서 효율적으로 소수만 구할 수 있는 알고리즘이다.

만약 1부터 n까지의 범위에 있는 수 중 소수를 모두 구하려면,

1. 크기가 n+1인 배열 생성 
   
   - index 와 수를 일치시키기 위해 n+1 크기로 배열을 생성한다.
   
   - 생성한 배열의 기본값을 모두 1로 채운다.
   
   - index 0과 index 1의 값은 0으로 설정한다. (index 0은 사용하지 않으므로 제외, 1은 소수가 아니므로 index 1 제외)
   
   

   let numbers = new Array(n+1).fill(1);
   numbers[0] = numbers[1] = 0;

   
   
   
2. 소수의 배수 제거
   
   - 소수(요소가 1인 index)를 찾아 해당 소수의 배수를 모두 0으로 바꾼다.
   
   - 배수를 제거하기 위해 소수를 선택하는 작업은 n의 제곱근까지만 진행한다.
      > n의 제곱근보다 큰 수 중 소수가 아닌 수는 다른 수의 배수로 제거된다.
   
   - 특정 소수의 배수를 제거하는 작업은 해당 소수의 제곱부터 시작한다.
      > 해당 소수의 제곱 미만의 배수들은 이미 이전에 처리된 소수의 배수에 의해 제거되었다.
      ex) 3의 배수를 찾을 때, 3*2, 3*3, 3*4 .... 순서로 배수를 찾게 되는데, 3*2=6은 이미 2*3으로 제거되었다.
   
   

   for (let i = 2; i <= Math.sqrt(n); i++) {
       if (!!numbers[i]) {
           for (let j = i*i; j <= n; j += i) {
               numbers[j] = 0;
           }
       }
   }

   
   
   
3. 소수 찾기
   
   - 값이 1인 요소의 index를 찾으면 된다.
   
   - 개수를 구할 경우 1의 개수를 구한다.
   
   

   //모든 소수
   let answer = [];
   for(let i = 2; i <= n; i++) {
      if(numbers[i]) answer.push(i);
   }
   return answer;
   
   //개수
   let cnt = 0;
   for(let num of numbers) {
      if(num) cnt++;
   }
   return cnt;