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

해당 수의 약수인지 아닌지 1부터 그 수까지 반복문을 돌려서 구할 수도 있지만, 효율성이 많이 떨어진다.

코테에서는 시간 초과가 될 가능성도 크다.

특히 특정 범위의 모든 수의 약수를 각각 구해야 하는 경우는 매우 비효율적이다.

---

소수를 효율적으로 구할 때 에라토스테네스의 체라는 알고리즘을 사용하는데, 역시나 같은 알고리즘을 사용할 수 있다.

에라토스테네스의 체는, 1부터 n까지의 수들의 배수를 차례대로 채워나가면서 효율적으로 약수의 개수를 구할 수 있는 알고리즘이다.

만약 1부터 n까지의 범위에 있는 모든 수의 약수의 개수를 각각 구하려면,

1. 크기가 n+1인 배열 생성 
   
   - index 와 수를 일치시키기 위해 n+1 크기로 배열을 생성한다.
   
   - 생성한 배열의 기본값을 모두 0으로 채운다.
   
   

   const numbers = new Array(num+1).fill(0);

   
   
   
2. 특정 수의 배수 추가
   
   - 특정 수(index)의 배수를 모두 +1한다.
   
   -  약수는 숫자의 전 범위에 걸쳐 나타날 수 있기 때문에, 소수와 다르게 전체 범위로 반복문을 돌린다.
   
   

   for (let i = 1; i <= num; i++) {
       for (let j = i; j <= num; j += i) {
           numbers[j]++;
       }
   }

   
   
   
3. 약수의 개수 찾기
   
   - 해당 index의 요소값 찾으면 된다. (배열 자체가 약수의 개수를 담고 있다!)