약수를 구하는 법

알고리즘 문제를 풀면서 한번에 약수를 처리하니 너무 시간이 오래걸렸다 그래서 방법을 찾아봤는데 그 중 2가지 방법이 좋아보여서 정리한다.

1. 제곱근을 이용한 방식

i의 약수를 찾기 위해 1부터 i까지 모든 수를 검사하는 것이 아니라, 1부터 √i까지만 검사하기 때문에 시간 복잡도가 줄어든다.
아래는 제곱근을 이용해 약수를 구하는 알고리즘 코드 중 일부이다.

let knights = [];

  for (let i = 1; i <= number; i++) {
    let divisor = 0;
    for (let j = 1; j <= Math.sqrt(i); j++) {
      // j의 범위는 1부터 √i까지
      if (i % j === 0) {
        // j가 i의 약수라면
        divisor++; // j는 약수
        if (j != i / j) {
          // j와 i / j가 다르면 (중복된 약수가 아닐 경우)
          divisor++; // i / j도 약수
        }
      }
    }
    knights.push(divisor); // i의 약수 개수를 knights 배열에 추가
  }

예를 들면 36의 약수 중 6은 서로 중복이기때문에 이런걸 처리하기위해 j!= i/j를 해준다.

2. 에라토스테네스의 체 방식

에라토스테네스의 체 라고 나도 이번에 알게되었는데 소수를 찾는 방법이라고 한다.
대충 먼저 1을 제거하고 2를 제외한 2의 배수를 제외하고 이런 방식인데
이 방식에 착안에 여기서는 반대로 약수를 모두 추가해주는 방식이다

let knights = Array(number + 1).fill(0); // 각 숫자의 약수를 저장할 배열

  // 모든 숫자의 약수를 미리 계산
  for (let i = 1; i <= number; i++) {
    for (let j = i; j <= number; j += i) {
      knights[j]++;
    }
  }

먼저 약수를 저장할 배열을 만들어 놓고 0으로 채운다. 그 후 한번에 모든수의 약수를 구하는 방식이다. 다만 이러면 배열에 첫번째는 0이므로 slice(1)을 사용해 제거해주고 사용하자