[Js] 약수 구하기

내가 수학을 다시 공부하다니. 기쁘다.

약수

어떤 정수를 나누어 떨어지게 하는 정수를 해당 정수의 약수라고 한다.
예를 들어 12의 약수는 1,2,3,4,6,12이다. 왜냐하면 이 숫자들로 12를 나누면 나머지가 0이 되기 때문이다.

약수 구하는 법

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

• 12의 약수를 구할 때 1부터 12까지 12를 나누었을 때 0이 되는 수를 저장하면 된다.
• 이 방법은 큰 숫자의 경우 시간이 많이 걸릴 수 있다.

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

// 사용 예시
console.log(getAllDivisors(12)); // 출력: [1, 2, 3, 4, 6, 12]

2. 주어진 수의 절반으로 약수 구하기

• 약수는 주어진 숫자의 절반보다 큰 수는 약수가 될 수 없기 때문에, 주어진 숫자의 절반까지만 반복하여 약수를 찾는다.
• 이 방법은 1번보다는 시간을 줄일 수 있어 효율적이다.

function getDivisorsUpToHalf(num) {
    let divisors = [];
    for (let i = 1; i <= num / 2; i++) {
        if (num % i === 0) {
            divisors.push(i);
        }
    }
    divisors.push(num); // 자기 자신도 약수에 추가
    return divisors;
}

// 사용 예시
console.log(getDivisorsUpToHalf(12)); // 출력: [1, 2, 3, 4, 6, 12]

3. Math.sqrt() 이용하기

• 주어진 숫자의 제곱근이 Math.sqrt(num)까지만 순환하여 약수를 찾는다.
• Math.sqrt(num)은 JavaScript의 내장 함수 중 하나로, 주어진 숫자 num의 제곱근을 반환합니다. 제곱근은 해당 숫자를 제곱했을 때 원래의 숫자가 되는 값을 의미합니다.
  예를 들어, Math.sqrt(25)는 25의 제곱근을 계산하여 5를 반환합니다. 이는 5를 제곱했을 때 25가 되기 때문입니다.
• Math.sqrt 함수를 사용하면 주어진 숫자의 제곱근을 빠르게 계산할 수 있으며, 순회할 범위가 줄어들기 때문에 효율적입니다.

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

// 사용 예시
console.log(getDivisors(12)); // 출력: [1, 2, 3, 4, 6, 12]

1. 반복문을 사용하여 1부터 숫자의 제곱근(Math.sqrt(num))까지 순회합니다.
   예를 들어, 숫자 28인 경우 getDividers(28)을 실행하면 i가 1부터 Math.sqrt(28)인 5까지 반복됩니다.
2. 각 숫자가 주어진 숫자 num을 나누어 떨어지는지 확인합니다.
   만약 나누어 떨어진다면 해당 숫자를 약수로 추가합니다.
   예를 들어, i가 1일 때 28%1 = 0이므로 1은 28의 약수입니다. 따라서 divisors 배열에 1이 추가됩니다.
   i가 2일 때 28%2=0이므로 2는 28의 약수입니다. 배열에 2도 추가됩니다.
   i가 5일 때 28%5는 0이 아니므로 5는 28의 약수가 아닙니다.
3. 동시에, 해당 숫자가 num / i와 같지 않은 경우에만 num / i를 추가합니다. 왜냐하면 이미 추가된 숫자와 동일하기 때문입니다.
4. 마지막으로, 약수 배열을 정렬하여 반환합니다.