아찌방 하우스

주소

풀이 - 나의 생각

효율적으로 약수를 구하는 방법을 알려드리고자 들고온 문제입니다.

보통 n의 약수를 구하기 위해서 사용하는 방법은

public int solution(int n) {
        int answer = 0;
        for(int i = 1; i <= n; i++){
            if(n%i == 0){
                answer+=i;
            } 
        }
        return answer;
}

위와 같이 1부터 n까지 반복문을 돌려

나머지가 0인 수를 찾는 것이겠죠?

그런데

약수라는 것은 숫자의 제곱근을 기준으로 대칭을 이룬다는 사실!!!!

알고 계셨나요???

요런 느낌입니다.

그러니까 반복문을 n의 제곱근까지 돌리면서

대칭하는 숫자도 같이 더하면

반복문의 횟수가 많이 줄어들겠죠?

하나 주의할 점은

약수의 개수가 홀수이면

대칭을 이루지 않는 약수가 있겠죠?

그것만 예외처리 해주면 됩니다.

코드

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) continue;
                answer+=(n/i);
            } 
        }
        return answer;
    }
}