[백준] 2501 약수 구하기

약수를 구하는 방법은 여러가지가 있는데 그 중에서 3가지 방법으로 문제를 풀이해보았다.

1. 약수

const divisors = [1];
for (let i = 2; i <= N; i++) {
  if (N % i === 0) {
    divisors.push(i);
  }
}
console.log(divisors[K - 1] ?? 0);

1~N까지 모든 수를 약수인지 확인하는 방법

2. 약수와 배수

const set = new Set();
for (let i = 1; i <= Math.floor(N / 2); i++) {
  if (N % i === 0) {
    set.add(i);
    if (N / i !== i) {
      set.add(N / i);
    }
  }
}
const divisors = [...set].sort((a, b) => a - b);
console.log(divisors[K - 1] ?? 0);

약수로 나누어 떨어지는 몫도 약수이기 때문에 같은 수로 나눈 경우가 아니라면 추가하는 방법이다. 중복 제거를 위해서 set를 사용했다. 예를 들어 6의 약수는 1,2,3,6인데 2로 나눴을 때와 3으로 나눴을 때 중복이 발생하기 때문이다.

3. 제곱근

const divisors = [];
for (let i = 0; i <= Math.sqrt(N); i++) {
  if (N % i === 0) {
    divisors.push(i);
    if (N / i !== i) {
      divisors.push(N / i);
    }
  }
}
divisors.sort((a, b) => a - b);
console.log(divisors[K - 1] ?? 0);

어떤 수의 제곱근까지만 약수를 확인하는 방법이다. 연산의 수가 가장 적기 때문에 가장 빠른 방법이라고 생각한다.

출처
백준 - 약수 구하기 https://www.acmicpc.net/problem/2501