프로그래머스 - 약수의 합 (자바)

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                answer += i;
                if (i != (n / i)) {
                    answer += n / i;
                }
            }  
        }
        return answer;
    }
}

n이 작다면 그냥 1부터 n까지 모든 수를 루프를 이용해서 n에 나눠서 확인하면 된다. 그런데 n이 커지면 비효율적이라 제곱근을 이용한 알고리즘을 이용하자.
A = B * C 에서 B로 A를 나누면 C가 나와서 B는 A의 약수이다. 그럼 C로 A를 나누면 B나와서 무조건 약수가 된다. 즉 약수는 짝으로 존재하니까 루프문에 다른 짝까지 체크하고 넘어가자는 게 위 알고리즘이다. 약수의 짝 중 작은건 무조건 N의 제곱근 안에 있으니 제곱근까지 확인하면서 짝들을 세면 된다. 여기서 짝이 같은 경우는 중복이니까
if (i != (n / i))을 체크하고 넘어가준다.