[알고리즘] 효율적으로 약수를 찾는 알고리즘

1. N 까지 순회하며 나머지 0 찾기

약수의 갯수를 N까지 순회하면 시간복잡도 O(N) 이 걸린다.

예) 100,0000 의 약수의 갯수를 찾아라.

100,000 % 1 = 0

100,000 % 2 = 0

100,000 % 3 = 1

…..

10만의 연산

또한 리스트 순회 도중에 각각의 원소에대한 약수의 갯수를 구해야되는 상황이면 O(N²) 이상의 엄청난 계산량이 걸릴 수 있다.

2. 제곱근 사용

<aside> 💡 N의 약수를 구할 때는, 1 ~ N의 제곱근 까지의 수가 N으로 나누어 떨어지는지 확인하면 된다.

제곱근 (= 루트) 예) √100 = 10

</aside>