약수 구하기

약수란 어떠한 수를 나눴을때 나머지가 0이되는 수들의 집합이다

 

모두 반복해서 찾기

function solution(n) {
  const divisors = [];
  for (let i = 1; i <= n; i++) {
    if (n % i === 0) divisors.push(i);
  }
  return divisors;
}

1부터 n까지 모두 순회해야하기때문에 시간복잡도가 n임

 

절반까지 찾기

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

예를들어 100의 약수는

1, 2, 4, 5, 10, 20, 25, 50, 100이다

본인인 100말고 제일큰 약수는 본인/2을 초과할 수 없으므로 반까지만 순회해도 된다

처음 방식 속도의 2배이다

 

제곱근 사용하기

function solution(n) {
  const divisors = [];
  for (let i = 1; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      divisors.push(i);
      if (n / i != i) divisors.push(n / i);
    }
  }
  divisors.sort((a, b) => a - b);
  return divisors;
}

약수의 특성상 약수를 나눠서 나온값도 약수이다

1, 100

2, 50

4, 25

5, 20

10, 10

 

번외

제곱근이 정수면 약수의 개수가 홀수이며

정수가 아니면 약수의 개수가 짝수다