약수 구하기

약수를 구하는 알고리즘에는 몇 가지 방법중 가장 일반적이고 효율적인 방법

1. 기본적인 방법:
   • 1부터 해당 숫자까지 모든 수로 나누어 보는 방법입니다.
   • 시간 복잡도: O(n)
2. 제곱근을 이용한 최적화 방법:
   • 숫자의 제곱근까지만 검사하는 방법입니다.
   • 시간 복잡도: O(√n)

제곱근을 이용한 최적화 방법의 알고리즘은 다음과 같습니다:

1. 주어진 수 n의 제곱근까지 반복합니다.
2. i가 n의 약수라면, i와 n/i 모두 약수입니다.
3. i와 n/i가 같지 않은 경우에만 두 수를 모두 약수 목록에 추가합니다.

예를들어 36의 약수를 구하면

	const res=[1];
    const divisor=n=>{
        let i=2;
        for(i; i<=Math.sqrt(n); i++) {
            if(n%i==0) {
                res.push(i);
                if(i != n/i) res.push(n/i);
            } 
        }
        res.push(i);
    };
    
    divisor(27);
    console.log(res.sort((a,b)=>a-b));

1. n = 36
2. Math.sqrt(36) = 6, 따라서 i는 1부터 6까지 반복합니다.
3. 반복 과정:
   • i = 1:
     36 % 1 === 0, divisors에 1 추가
     36 / 1 = 36, divisors에 36 추가
     divisors = [1, 36]
   • i = 2:
     36 % 2 === 0, divisors에 2 추가
     36 / 2 = 18, divisors에 18 추가
     divisors = [1, 36, 2, 18]
   • i = 3:
     36 % 3 === 0, divisors에 3 추가
     36 / 3 = 12, divisors에 12 추가
     divisors = [1, 36, 2, 18, 3, 12]
   • i = 4:
     36 % 4 === 0, divisors에 4 추가
     36 / 4 = 9, divisors에 9 추가
     divisors = [1, 36, 2, 18, 3, 12, 4, 9]
   • i = 5:
     36 % 5 !== 0, 아무 작업 안 함
   • i = 6:
     36 % 6 === 0, divisors에 6 추가
     36 / 6 = 6, 이미 6이 있으므로 추가하지 않음
     divisors = [1, 36, 2, 18, 3, 12, 4, 9, 6]
4. 정렬:
   divisors.sort((a, b) => a - b)
   결과: [1, 2, 3, 4, 6, 9, 12, 18, 36]

최종 출력: [1, 2, 3, 4, 6, 9, 12, 18, 36]

이 알고리즘의 장점:

1. 제곱근까지만 검사하므로 효율적입니다.
2. 각 약수를 찾을 때 그 약수의 쌍도 함께 찾아 시간을 절약합니다.
3. 마지막에 정렬하여 약수들을 순서대로 반환합니다.

이 방법은 큰 수의 약수를 구할 때도 효율적으로 작동합니다.