[코딩테스트/Javascript] 약수와 약수 찾기

코딩테스트를 풀면서 약수를 찾아야하는 문제가 자주 출제되어 활용할 수 있는 코드를 정리했습니다

 

약수란 어떤 수를 나누어 떨어지게 하는 수를 의미합니다

1의 약수 → 1

10의 약수 → 1, 2, 5, 10

100의 약수 → 1, 2, 4, 5, 10, 20, 25, 50, 100

 

n의 약수는 a x b 의 형태로 쌍을 이루기 때문에 n의 모든 약수를 찾아야 한다면 n의 제곱근까지만 확인한다면 n의 모든 약수를 찾을 수 있습니다

 

 

 

위의 예시에서 n이 36이라면, 1부터 n의 제곱근인 6까지만 확인한다면 n = a x b의 형태에서 b  = n / a 계산으로 함께 구할 수 있습니다 단, 6x6과 같이 두 약수가 동일한 경우라면 중복이 발생하기 때문에 이 경우에는 중복 없이 한번만 약수를 카운트하는 조건이 필요합니다

 

 

모든 약수 찾기

function getDivisors(n) {
  const divisors = [];

  for (let i = 1; i * i <= n; i++) {
    if (n % i === 0) {
      divisors.push(i);

      if (i !== n / i) divisors.push(n / i);
    }
  }

  return divisors;
}

 

 

약수의 개수 찾기

function countDivisors(n) {
  let count = 0;

  for (let i = 1; i * i <= n; i++) {
    if (n % i === 0) {
      count++;

      if (i !== n / i) count++;
    }
  }

  return count;
}

 

 

소수 찾기 및 에라토스테네스의 체 알고리즘 글 보러가기 →

[코딩테스트] 소수 찾기와 에라토스테네스의 체