[Programmers/Java/Lv.1/수학 유형] 18.약수의 합

문제 설명

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

 

제한 사항

• n은 0 이상 3000이하인 정수입니다.

 

입출력 예

n	return
12	28
5	6

• 입출력 예 #1 : 12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다.
• 입출력 예 #2 : 5의 약수는 1, 5입니다. 이를 모두 더하면 6입니다.

 

풀이1

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

 

풀이2

/*
절반(제곱근)으로 돌려 for문의 성능 향상

num의 제곱근까지만 돌아도 된다!
약수는 √n을 기점으로 서로 짝을 이루기 때문에 n까지 돌 필요 없이 √n까지만 반복문을 돌면 된다.

*/

class SumDivisor {
    public int sumDivisor(int num) {
        int answer = 0;
    	for(int i =1 ; i<=num/2;i++)
      		if(num%i==0) answer+=i;

        return answer + num;
    }

    public static void main(String[] args) {
        SumDivisor c = new SumDivisor();
        System.out.println(c.sumDivisor(12));
    }
}

• 1부터 num/2까지만 돌고,
• 마지막에 + num을 따로 더함
• 이유: 어떤 수의 자기 자신을 제외한 약수는 무조건 num/2 이하이기 때문
• 예: 12의 약수는 1, 2, 3, 4, 6, 12 → 12를 빼면 나머지는 12/2 이하
• ⏱ 성능 상 이득이 있음 → 반복 횟수가 n이 아닌 n/2