[JavaScript] 약수 구하기

1. 약수(Divisor)란 무엇인가?

약수는 어떤 수를 나누어 떨어지게 하는 수이다.

 

예를 들어,

2의 약수는 1, 2이다.

3의 약수는 1, 3이다.

4의 약수는 1, 2, 4이다.

5의 약수는 1, 5이다.

...

 

 

2. 약수 구하기

약수의 정의를 이용하면 어떤 수의 약수를 구할 수 있다. 어떤 수 N을 1, 2, 3, ... , N으로 나눴을 때 나누어 떨어지는 수를 찾으면 된다. 이를 JavaScript 코드로 표현해 보자.

const getDivisors = (N) => {
  const divisors = [];
  for (let i = 1; i <= N; i++) {
    if (N % i === 0) divisors.push(i);
  }
  return divisors;
};

 

 

3. 약수 구하기 - Upgrade ✨

어떤 수 N의 약수는 자기 자신을 제외하고는 N/2보다 클 수 없다!

 

따라서 어떤 수 N을 1, 2, 3, ..., N/2으로 나눴을 때 모두 나누어 떨어지는 수를 찾고, 자기 자신인 N을 추가하면 된다. 위의 방법보다 for문 반복 횟수가 줄어든다.

const getDivisors = (N) => {
  const divisors = [];
  for (let i = 1; i <= N / 2; i++) {
    if (N % i === 0) divisors.push(i);
  }
  // 마지막으로 자기 자신을 추가해야 함!
  divisors.push(N);
  return divisors;
};

 

 

4. 약수 구하기 - Upgrade ❓

어떤 수 N의 약수는 항상 쌍으로 존재한다. 곱해서 N이 되는 짝꿍이 있다는 뜻!

 

예를 들어,

8의 약수는 1, 2, 4, 8이다. 1과 8, 2와 4를 곱하면 8이 된다.

9의 약수는 1, 3, 9이다. 1과 9, 3과 3을 곱하면 9가 된다. (3과 3도 쌍이라고 치자..)

 

N이 $\sqrt{N}$보다 작거나 같은 어떤 자연수 M으로 나누어 떨어진다면, N/M도 N의 약수가 된다!

const getDivisor = (N) => {
  const divisors = [];
  const sqrtN = Math.sqrt(N);
  for (let i = 1; i <= sqrtN; i++) {
    if (N % i === 0) {
      divisors.push(i);
      // N/i === i인 경우 N/i값을 추가하면 중복 저장되므로 주의
      if (N / i !== i) divisors.push(N / i);
    }
  }
  return divisors;
};

단, 이 방법의 경우 약수가 오름차순으로 저장되지 않음에 주의한다!