약수의 합

코딩테스트 연습 - 약수의 합 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 1에서부터 n까지 n이 i 로 나누어 떨어지면 answer 의 i 값들을 더함
        for(int i=1; i<=n;i++){
            if(n%i == 0){
                answer = answer + i;
            }
        }
        return answer;
    }
}


// 여기서는 숫자가 3000이하인 정수이기 때문에 이렇게해도 시간복잡도가 오래걸리지는 않지만 
// 만약 숫자가 더 크다면 이렇게 하는게 시간복잡도 면에서 좋음

 	int sum = 0;
    int sqrt = (int) Math.sqrt(number);
    for (int i = 1; i <= sqrt; i++) {
        if (number % i == 0) {
            sum += i;
            if (i != number / i) { 
	// i와 number/i가 같지 않으면 (제곱근이 아니면) 둘 다 더함
                sum += number / i;
            }
        }
    }
    return sum;