[Algorithm] 약수의 개수 구하기 - 제곱수의 약수의 개수는 홀수임을 활용

 

제곱수의 특성과 제곱수의 약수의 개수

• 제곱수의 약수의 개수가 홀수인 것은 제곱수의 특성 때문
• 제곱수는 항상 어떤 수를 제곱한 형태
  • 그 약수는 쌍을 이루는 약수들이 있고, 그 가운데 제곱한 수 자신만이 쌍을 이루지 않는 약수로 홀수개의 약수를 가지게 됨
  • 예를 들어 16 (4 X 4) 이라는 제곱수일때, 16의 약수는 1, 2, 4, 8, 16인데, 이 약수들 중에서 1과 16은 쌍을 이루고 2와 8은 쌍을 이룸.
  • 그러나 4는 쌍을 이루지 않는 유일한 약수
  • 따라서 16의 약수는 총 5개로 홀수

---

제곱근 활용했을 때와 아닐 때의 코드 효율성

 

 

제곱근 활용하지 않았을 때 (for 반복문 사용)

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

const isDivisorCountOdd = (num) => {
  const divisors = findDivisors(num);
  return divisors.length % 2 !== 0;
};

console.log(isDivisorCountOdd(16));  // true
console.log(isDivisorCountOdd(15));  // false

• findDivisior 함수 : 주어진 숫자의 모든 약수를 찾아 배열로 반환하는 함수
• isDivisorCountOdd : findDivisor 함수를 호출해 약수의 배열을 얻은 다음, 배열의 길이가 홀수인지 여부를 반환하는 함수
• 이는 16(제곱수) 일때 약수의 개수가 홀수이고, 15(안 제곱수)는 약수의 개수가 짝수임을 보여줌
• 하지만, 이런 방식은 숫자가 커질수록 많은 계산을 필요로 함.

제곱근 활용했을 때 (Math.sqrt() 사용)

const isSquareNumber = (num) => {
  return Number.isInteger(Math.sqrt(num));
};

console.log(isSquareNumber(16));  // true
console.log(isSquareNumber(15));  // false

• isSquareNumber 함수는 주어진 숫자의 제곱근이 정수인지 확인해 제곱수인지 판별하는 함수
• 즉, isSquareNumber(16)은 true를 반환하고, 15일때는 false를 반환함
• 이는 위의 isDivisorCountOdd 함수와 동일한 결과를 반환하지만 계산 효율성 면에서 훨씬 우수함