[Algorithm] 약수 구하기

KJA·2022년 10월 13일
0

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

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

주어진 수의 절반만 확인하기

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

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

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);
        }
    }
    
    // divisors.sort((a, b) => a - b);
    return divisors;
}

num 을 100이라고 가정하자.
Math.sqrt(100) = 10이라는 값이 도출된다.

그러면 어떻게 10까지만 숫자를 체크하는데 나머지 약수 값들을 구할 수 있는 걸까?
코드를 보면 알겠지만 해당 약수를 가지고 입력받은 값을 나누게 될 경우 나오는 결과 값 역시 약수이기 때문이다.
100의 약수를 10 이하의 숫자만 나열하면 [1, 2, 4, 5, 10]이다.

하나씩 나누어 본다면
100 / 1 = 100
100 / 2 = 50
100 / 4 = 25
100 / 5 = 20
100 / 10 = 10

이런 식으로 값이 이루어진다.
그래서 최종적으로 100의 약수는 다음과 같다.
[1, 2, 4, 5, 10, 20, 25, 50, 100]

코드 로직 상  [1, 100, 2, 50, 4, 25, 5, 20, 10] 이런 식의 배열을 가지게 되는데,
순서대로 뽑아야 한다면 당연히 정렬을 한번 실행해 주어야 한다.

(중간에 if 구문 안에 또다시 if구문을 한 이유는 중복된 값을 제외시켜준 것이다. new Set을 통해 중복을 제거해주어도 좋고 아니면 그냥 예제처럼 제외시켜줘도 좋다.)


https://mine-it-record.tistory.com/522

0개의 댓글