약수의 개수

1 〰️ N 까지 각각 약수의 개수, 총 개수 구하기

class Solution {
    public int solution(int number) {
        int[] count = new int[number + 1];
        for (int i = 1; i <= number; i++) {
            for (int j = 1; j <= number / i; j++) {
                count[i * j]++;
            }
        }
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            System.out.println(i + " " + count[i]);
        }
        return answer;
    }
}

이 로직은 1부터 N까지의 약수의 개수를 구할 때인 특수한 경우에만 가능하다. n부터 m까지의 약수의 개수 구하기는 해당이 되지 않으니 주의해야한다. 각각의 약수의 개수는 count 배열에 들어가 있어서 조회 가능하고 총 개수는 다 더하면 된다. 시간 복잡도는 nO(logn)이고 다양한 방법이 있지만 내가 알고있는 로직 중에서는 가장 효율적인 방법이다. 더 좋은 방법 있으면 알려주세요...

 

 

N 〰️ M까지의 약수의 총 개수 구하기

class Solution {
    public int solution(int n, int m) {
        int answer = 0;
        for (int i = n; i <= m; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (j * j == i)
                    answer++;
                else if (i % j == 0)
                    answer += 2;
            }
        }
        System.out.println(answer);
        return answer;
    }
}

간단하게 해석하면 각 수의 내부 반복문에서 제곱근까지만 순회하는 방법이다. 여기서 제곱근일 때는 1을 더해주고 아닐 때는 2씩 더해준다. 이 코드를 조금만 응용하면 각 수의 약수와 약수의 개수도 구할 수 있다. 시간 복잡도는 nO(√n)이고 위의 방법보다는 느리지만 가장 기본적인 방법에서는 비교적 효율적이다.

 

시간나면 더 다양한 방법들 추가해야겠다.