JS, 약수구하기

기존의 반복문으로 주어진 수의 절반을 대상으로 확인하기를 하니 코테 문제 시간초과가 뜸

더 효율적인 방법이 필요하여 방법을 찾아보고 정리

 

[ 제곱근 사용하기 ]

약수를 구하고자 하는 수를 n이라고 하면 1 ~ √n 범위로 n의 약수를 구함

n의 약수를 나누었을 때 값 또한 n의 약수

√n의 값이 정수로 떨어질 경우 약수와 나누었을때의 값으로 넣은 약수가 중복되므로 중복제거를 해야함

 

▶ 약수 구하는 코드

조건문 사용

const getDivisors = (num) => {
    let result = [];
    for(let i = 1 ; i <= Math.sqrt(num) ; i++){
        if(num % i === 0) {
            result.push(i);
            if(num / i != i) result.push(num / i);	//중복 제거
        }
    }
    result.sort((a, b) => a - b);	//오름차순 정리
    return result;
}

 

Set 사용

const getDivisors = (num) => {
    let result = [];
    for(let i = 1 ; i <= Math.sqrt(num) ; i++){
        if(num % i === 0) result.push(i, num/i);
    }
    result.sort((a, b) => a - b);	//오름차순 정리
    return Array.from(new Set(result));	//중복제거
}

 

▶ 약수 개수 구하는 코드

위의 코드의 배열의 length, set한 상태로 size를 구하거나 혹은

 

const getDivisors = (num) => {
    let result = 0, n = Math.sqrt(number);
    for(let i = 1 ; i < n ; i++){
        if(num % i === 0) result++;
    }
    return n === Math.floor(n) ? result * 2 + 1 : result * 2	//제곱근의 정수로 떨어질 경우 +1, Ex)100->10
}