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

문제 설명

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

 

제한 사항

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

 

프로그래머스

 

 

1차 풀이 코드

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(int n) {
        var list = new List<int>();
        for (int i = 1; i <= n / 2; i++)
        {
            if (list.Contains(i)) continue;

            for (int j = i; j <= n; j++)
            {
                if ((i * j) > n) break;

                if ((i * j) % n == 0)
                {
                    if (i == j)
                    {
                        list.Add(i);
                    }
                    else
                    {
                        list.Add(i);
                        list.Add(j);
                    }
                    
                    break;
                }
            }
        }
        
        if (list.Count == 0)
        {
            list.Add(n);
        }
        
        return list.Sum();
    }
}

 

일단 풀긴 풀었는데 확실히 이거보다 좋은 방법이 있을거라는 생각이 든다.

 

약수의 규칙을 찾아보자

 

2차 풀이 코드

using System;

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

 

좀 더 최적화된 코드를 찾아냈다. 훨씬 좋아졌다.

 

같이 보면 좋은 글

약수(수학) - 나무위키