[프로그래머스] 약수의 합

문제

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

 

제한사항

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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12928

프로그래머스

풀이[c++]

#include <string>
#include <cmath>
#include <vector>

using namespace std;

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

숫자의 약수는 그 수의 제곱근보다 작거나 같은 값에서 나눠질 때 나누는 값과 몫이 모두 약수가 된다.

예시) 8의 경우, 루트 8은 2보다 크고 3보다 작다. 따라서 1에서 2까지 8을 나눠보면 몫이 4와 8이 나온다.

         따라서 8의 약수는 1, 2, 4, 8 임을 알 수 있다.

단, 이에 한 가지 예외가 있는 데 어떤 숫자의 제곱은 약수가 중복되게 되는 데 이를 빼주어야 한다.

예시) 25의 경우, 루트 25는 5이다. 따라서 1에서 5까지 25을 나눠보면 몫이 5와 25가 나온다.

이 때 5을 고려하지 않으면  25의 약수는 1, 5, 5, 25로 5가 두 번 들어가게 된다.