약수 구하기 알고리즘
단순하게 모든 수를 나눠서 약수를 구한다면 시간 복잡도에 있어 그렇게 좋은 코드가 아니다.
그래서 주어진 수의 절반을 대상으로만 확인하는 방법이 있는데
int divisor_cnt(int n) {
int cnt = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
cnt++;
if (n / i != i) cnt++;
}
}
return cnt;
}
C++
복사
바로 제곱근을 이용하는 방식이다.
해당 약수를 가지고 입력받은 값을 나누게 될 경우 나오는 결과 값 역시 약수이기 때문에 원하는 값을 구할 수가 있다.