1. 약수 구하기

---

약수

• 자신을 1 부터 자기 자신까지 나누었을 때 나머지가 0인 되는(나누어 떨어지는) 경우

• a를 b로 나누었을 때 나머지가 0이면 b는 a의 약수이다.

// 5를 1 부터 자기 자신까지 나누었을 때 나머지가 0인(나누어 떨어지는) 1, 5가 5의 약수이다.
5 % 1  // 0
5 % 2  // 1
5 % 3  // 2
5 % 4  // 1
5 % 5  // 0 

1) 중첩 for문 사용

• 두 수 i와 j를 곱해서 num이 나오면 i와 j는 num의 약수가 되므로, i * j === num이 되는 조건 일 때, 3 * 4, 4 * 3 같은 중복을 방지하기 위해 i의 값만 빈 배열에 담아준다.

function getSumOfFactors(num) {
  let result = [];

  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      if (i * j === num) {
        result.push(i);
      }
    }
  }
  return result;
}

2) 나머지 연산자(%) 사용

• num을 i로 나눴을 때 나누어 떨어진다면 i는 num의 약수이므로, 나누어 떨어지는 모든 i를 구한다.

function getSumOfFactors(num) {
  let result = [];

  for (let i = 1; i <= num; i++) {
    if (num % i === 0) {
      result.push(i)
    }
  }

  return result;
}

3) 주어진 수의 절반을 대상으로만 확인하기

• 위의 방법처럼 단순히 1 부터 자기자신까지 모두 나눠보면서 구하는 방식은 시간복잡도에 있어서 좋은 방법이 아니다.

• 약수는 자기자신을 제외하고는 자기자신 / 2 보다 클 수 없기 때문에 1 부터 자기자신 / 2 까지만 나눠보면서 구한다.

function getSumOfFactors(num) {
  let result = [];

  for (let i = 1; i <= num / 2; i++) {
    if (num % i === 0) {
      result.push(i)
    }
  }

  return result;
}

4) 제곱근(Math.sqrt) 사용하기

• 제곱근을 사용하는 방법이 위의 방법들 보다 가장 빠르다.

• 나누어지는 수(아래에서 number)의 제곱근 이하의 수로 나누어서 구한 약수들로 나누어지는 수를 나누게 될 경우 나오는 수 역시 나누어지는 수의 약수인 원리를 이용한다.

• number가 100이라면 100의 제곱근 10 이하의 수로 100을 나누어서 100의 약수를 구해보면 [1, 2, 4, 5, 10]이 나온다. 다시 100을 1, 2, 4, 5, 10으로 각각 나누어 보면 나오는 수들도 다 100의 약수임을 알 수 있다.

• 100 / 1 = 100

• 100 / 2 = 50

• 100 / 4 = 25

• 100 / 5 = 20

• 100 / 10 = 10

• divisors.push(i); 라인에서 [1, 2, 4, 5, 10]이 나오고, divisors.push(number / i); 라인에서 [100, 50, 25, 20, 10]이 나오게 된다. 그러나 로직의 순서 상 오름차순이 아니라서 별도의 오름차순이 필요하다.

• if문 안에 !divisors.includes(number / i) 이 조건을 주는 이유는 중복값을 제거하기 위함이다.

function solution(number) {
    let divisors = [];

    for (let i = 1; i <= Math.sqrt(number); i++) {
        if (number % i === 0) {
            divisors.push(i);
            if (!divisors.includes(number / i)) {
                divisors.push(number / i);
            }
        }
    }

    return divisors;
}

2. 약수의 합 구하기

---

1) 중첩 for문 사용

• 두 수 i와 j를 곱해서 num이 나오면 i와 j는 num의 약수가 되므로, i * j === num이 되는 조건 일 때, 3 * 4, 4 * 3 같은 중복을 방지하기 위해 i의 값만 더해준다.

function getSumOfFactors(num) {
  let result = 0;

  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      if (i * j === num) {
        result = result + i;
      }
    }
  }
  return result;
}

2) 나머지 연산자(%) 사용

• num을 i로 나눴을 때 나누어 떨어진다면 i는 num의 약수이므로, i는 1부터 num까지 i로 나누어 떨어지는 i의 모든 합을 구한다.

function getSumOfFactors(num) {
  let result = 0;

  for (let i = 1; i <= num; i++) {
    if (num % i === 0) {
      result = result + i;
    }
  }

  return result;
}