제곱근이 정수면 약수의 갯수는 홀수이다....Number.isInteger(Math.sqrt(i))

알고리즘 문제를 풀다가 생각지 못한 개념이 나와서 정리한다.

문제)

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항 : 1 ≤ left ≤ right ≤ 1,000

입출력 예)

left	right	result
13	17	43
24	27	52

• 나의 풀이

function solution(left, right) {
  const arr = [];
  let divisor = [];
  let answer = 0;
  for (let i = 0; i < Math.abs(right - left) + 1; i++) {
    arr.push(Math.min(left, right) + i);
  }
  for (let i = 0; i < arr.length; i++) {
    for (let j = 1; j <= arr[i]; j++) {
      if (arr[i] % j === 0) divisor.push(arr[i]);
    }
    divisor.length % 2 === 0 ? (answer += arr[i]) : (answer -= arr[i]);
    divisor = [];
  }

  return answer;
}

일단 left right는 제한사항에 있는데 내가 굳이 넣은거 같고 먼저 left 부터 right까지 숫자들을 구하고 약수가 짝수이면 더하고 홀수이면 빼게 만들었다.

그런데 다른사람풀이중에 매우 간단하게 푼 풀이가 있었다.

function solution(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}

바로 제곱근이 정수이면 약수의 갯수가 홀수 라는 개념으로 문제를 푼 것이다.

제곱근은 약수가 중복이 되기 때문에 다른 약수들은 짝으로 이루어져있고 제곱근은 한개이기 때문에 약수의 총 갯수는 홀수가 나오게 된다(ex. 16 => (1,12),(2,8),(4,4) 4가 중복이라 총개수는 홀수임)

...
...
...
수학을 잘하자!