[알고리즘/JS] 약수구하기

약수란 어떤 자연수를 나누어 떨어지게 하는 수이다
ex) 12의 약수: 1,2,3,4,6,12

약수를 구하는 방법 세가지를 알아보자

1. 모든 수를 나눠서 약수 구하기

const num = 12; // 약수를 찾기 위한 정수 설정
const result = [];
let index = 1;

while (index <= num) {
  if (num % index === 0) {
    result.push(index);
  }
  index++;
}
console.log(result); // [ 1, 2, 3, 4, 6, 12 ]

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

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

const num = 12;
let result = [];
let index = 1;

while (index <= num / 2) {
  if (num % index === 0) {
    result.push(index);
  }
  index++;
}
result = [...result, num]; // 본인 값 추가까지 추가
console.log(result); // [ 1, 2, 3, 4, 6, 12 ]

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

• 1 ~ num의 제곱근 범위로 num의 약수 구하기
  ex) Math.sqrt(100) = 10
  num이 100이면 1~10 까지 나눠서 나머지가 0 인 값 구한다.
  [1,2,4,5,10]
  num을 위의 약수로 나누었을때 값 역시 num의 약수
  100 / 1 = 100
  100 / 2 = 50
  100 / 4 = 25
  100 / 5 = 20
  100 / 10 = 10 → 중복
  [1, 2, 4, 5, 10, 10, 20, 25, 50, 100]
  중복제거하기

const num = 100;
const result = [];
let index = 1;

while (index <= Math.sqrt(num)) {
  if (num % index === 0) {
    result.push(index);
    if (num / index !== index) {
      result.push(num / index);
    }
  }
  index++;
}
result.sort((a, b) => a - b);

console.log(result); // [ 1, 2, 4, 5, 10, 20, 25, 50, 100 ]