약수의 개수 구하는 방법
숫자 N의 약수의 개수를 구하는 문제가 주어졌을 때, 1부터 N까지 모두 탐색을 하게 되면, N이 100,000같이 크기가 클 경우 시간이 많이 걸린다. 약수 개수를 구할 때, 시간을 줄이는 방법은 2가지가 있다. 1/ 소인수분해를 이용하는 방법 N을 소인수분해하여 각 소수의 지수를 구한 후, (각 지수+1) 값들을 곱하여 약수의 개수를 구한다. ex) N이 24일 경우 24 = 2³ * 3¹ → (3 + 1) * (1 + 1) = 4 * 2 = 8 즉, 24의 약수의 개수는 8이 된다. (1, 2, 3, 4, 6, 8, 12, 24) 2/ N의 제곱근으로 범위를 좁혀 탐색 만약 N이 24일 경우, 24의 제곱근(√24)은 4.xxxx이다. 따라서 1~24가 아닌, 1~4까지만 탐색해도 [ 1, 2, 3..
