알고리즘_약수 구하기

약수?

어떤 수를 나누어떨어지게 하는 수

1.단순하게 약수 구하는 방법

1부터 약수의 크기까지 반복해서 돌면서 나누어 떨어지는 수 구하기

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

• 1부터 특정 숫자까지의 약수 구하기

for (let i = 1; i <= number; i++) {
  const divisors = [];
  for (let j = 1; j <= i; j++) {
    if (i % j === 0) divisors.push(j);
  }
}

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

약수는 본인을 제외하고 n/2 보다 클 수 없기 때문에 절반값까지만 체크

자기 자신은 빠져있기 때문에, 마지막에 자기 자신 추가하기

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

• 1부터 특정 숫자까지의 약수 구하기

for (let i = 1; i <= number; i++) {
  const divisors = [];
  for (let j = 1; j <= i / 2; j++) {
    if (i % j === 0) {
      divisors.push(j);
    }
    divisors.push(i);
  }
}

3.제곱근 사용하기

약수를 가지고 입력받은 값을 나누게 될 경우 나오는 결과 값 역시 약수이기 때문

const getDivisors = (num) => {
  const divisors = [];
  for (let i = 1; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      divisors.push(i);
      if (num / i != i) divisors.push(num / i);
    }
  }

  return divisors;
};

■ 예시 (100의 약수 구하기)

const getDivisors = (num) => {
  const divisors = [];
  for (let i = 1; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      divisors.push(i);
      if (num / i != i) divisors.push(num / i);
      console.log(num + "/" + i + "=" + num / i);
      // 100 / 1 = 100
      // 100 / 2 = 50
      // 100 / 4 = 25
      // 100 / 5 = 20
      // 100 / 10 = 10
    }
  }

  return divisors;
};
getDivisors(100);
// [1, 2, 4, 5, 10, 20, 25, 50, 100]

■ 예시 (36의 약수 구하기)

const getDivisors = (num) => {
  const divisors = [];
  for (let i = 1; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      divisors.push(i);
      if (num / i != i) divisors.push(num / i);
      console.log(num + "/" + i + "=" + num / i);
      //   36 / 1 = 36
      //   36 / 2 = 18
      //   36 / 3 = 12
      //   36 / 4 = 9
      //   36 / 6 = 6
      //   36 / 1 = 36
      //   36 / 2 = 18
      //   36 / 3 = 12
      //   36 / 4 = 9
      //   36 / 6 = 6
    }
  }

  return divisors;
};
getDivisors(36);
// [ 1, 36, 2, 18, 3, 12, 4, 9,  6 ]

참고 사이트

• [알고리즘] 약수 구하기 알고리즘 by javascript