개발자로 살아남기

약수의 총 합 구하기

프로그래머스의 약수의 총 합을 풀었는데 정석의 방법으로 풀었었다.

int answer = 0;

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

return answer;

다른 풀이를 보니 아래와 같이 풀었는데, 그 이유는 간단했다.

int answer = 0;

for(int i=1; i<=n / 2; i++){
    if (n % i == 0){
        answer += i;
    }
}

answer += n;

return answer;

for문의 조건에서 n/2를 한 이유는 약수는 n의 절반이 넘는 값이 나올 수 없기 때문인데

예를들어, 12의 경우 약수는 1, 2, 3, 4, 6, 12이며 1x12 == 2x6 == 3x4 == 12 로 계산이 가능하다.

따라서 어떤 수가 들어오더라도 n의 약수 중 n의 절반이 넘는 값이 약수가 될 수 없다.

그래서 아래 풀이의 경우 연산횟수를 절반으로 줄일 수 있다.