[TIL] 약수 개수를 구하는 알고리즘

1️⃣ 흔히 알고있는 약수 개수를 구하는 방법

✅ 나머지가 0이 되는 값을 구하는 방법

아래의 코드는 흔히 접하고, 알고 있는 약수 개수를 구하는 방법이다.
약수의 개수를 구하려는 number를 1부터 number까지 나눠서 0이 되는 값을 카운트 해서 구하는 방법이다.
하지만 아래와 같은 방법은 숫자가 커지게 되면, 그만큼 시간이 오래걸려서 좋지 않은 방법이 된다.
그래서 효율적으로 약수 개수를 구하는 방법을 찾아보고 공부해 봤다.

// 약수의 개수를 구하는 함수
func measure(_ number: Int) -> Int { 
    
    var count = 0;
    
    for i in 1...number { 
        if number % i == 0 { 
			count += 1;
        }
    }
    return count;
}

2️⃣ 효율적인 약수 개수를 구하는 방법

✅ number의 제곱근을 구해서 하는 방법

number의 제곱근의 약수의 개수에서 중복된 수를 제거하고 X2를 하게 되면, number의 약수의 개수를 구할 수 있다.
아래의 알고리즘이 이 원리를 이용한 방법이다.

func measure(_ number: Int) -> Int { // 병사 번호의 약수개수를 구하는 함수
    
    var count = 0;
    
    for i in 1...Int(sqrt(Double(number))) { // number의 제곱근을 구한다 ex) 100의 제곱근은 10이기 때문에 1...10
        if number % i == 0 { // 나머지가 0일때 ex) 1, 2, 5, 10
            if i * i == number { // 나눈 수가 제곱근이면, 중복이 되기 때문에 카운트가 +1 ex) 제곱근인 10은 중복
                count += 1;
            } else{ // 나눈 수가 제곱근이 아니면, 중복이 아니기 때문에 +2 ex) 1, 2, 5 <=> 100, 50, 20 이기 때문에 +2
                count += 2;
            }
        }
    }
    return count;
}