[Algorithm] 약수의 합

문제 설명

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

 

문제 유형

• 약수 구하기

 

의사코드

1. 총합을 저장할 변수(sum)를 선언한다.
2. [반복문] 2부터 √N까지 반복한다.
   1. 만약 N을 나누었을 때 나머지가 0이라면
      1. 나눈 수와 몫을 sum에 더한다.
      2. 나눈 수와 몫이 동일한 값이라면 한 번만 더한다.
3. 총합(sum)을 반환한다.

 

코드 작성

int solution(int num) {
    int sum = 0;
    int rootNum = sqrt(num);
    
    for (int div = 1; div <= rootNum; div++)
    {
        if (num % div == 0)
        {
            sum += div;
            
            int quotient = num / div;
            if (quotient != div)
            {
                sum += quotient;
            }
        }
    }
    return sum;
}

 

 

배운 점

• N의 약수를 구하려면 1부터 N의 제곱근까지만 반복하면 된다.
  • 이유는 약수의 최대 값은 N이다. (1 x N)
  • 약수 a가 √N보다 크면, 그에 대응하는 약수 b는 √N보다 작아진다.
  • 그러나 √N보다 작은 수는 a를 탐색하면서 이미 확인된 약수이다.
  • 따라서 a <= √N까지 탐색하면 모든 약수를 구할 수 있다.
• 시간 복잡도는 O(√N)가 된다.