약수의 개수 알고리즘
·
Algorithm
public int countDivisor(int num) { double sqrt = Math.sqrt(num); int count = 1; for (int i = 2; i 1부터 n까지의 숫자를 i로 나누어 떨어지는 수를 count 에 더하면 시간 복잡도가 O(n)이 나오게 된다.하지만, 약수의 개수를 구할 때에는 해당 숫자의 제곱근까지만을 구한 후 2배를 해주면 된다. 20을 예로 들자면, 20의 제곱근은 4.xxx이다.20을 1부터 4까지 각각 나누어서 나누어 떨어지는 수는 아래와 같다. 20 % 1 = 020 % 2 = 020 % 3 = 220 % 4 = 0 따라서 1, 2, 4는 20의 약수가 된다.이번엔 1, 2, 4로 20을 나누게 되면 아래와 같다. 20 / 1 = 20..