프로그래머스의 "약수의 개수와 덧셈" 문제를 풀다가 1~N까지 다 계산해보는 $O(n)$의 방식으로 해야하나? 싶어서 약수의 개수를 구하는 법을 찾아봤다.

증명은 아직 수학 실력이 부족해서 몇 가지 주어진 수들을 사용해서 직접 예를 들어보겠다.

주어진 수의 약수는 제곱근을 제외하고 짝을 이룬다.

주어진 수 = 10, 10의 약수 = [1, 2, 5, 10]

약수1	약수2	곱한 값
1	10	10
2	5	10

위 표처럼 약수들은 서로 곱해지면 주어진 수가 되며 짝을 이룬다.

약수가 정수이고 제곱근인 경우는?
주어진 수 = 9, 9의 약수 = [1, 3, 9]

약수1	약수2	곱한 값
1	9	9
3	3	9

정수 3이 9의 제곱근이자 약수인 경우에는 짝인 1과 9, 그리고 제곱근인 3이 약수를 이룬다.

약수 중에 절반만 구하면 나머지 절반은 구할 필요가 없다.

144의 약수 중 절반인 1, 2, 3, 4, 6, 8, 9를 알고 있다면
그 약수들로 144를 나누면 나머지 절반 약수를 알 수 있다.

주어진 수	약수	나눈 수
144	1	144
144	2	72
144	3	48
144	4	36
144	6	24
144	8	18
144	9	16
144	12	12
144	16	9
144	18	8
144	24	6
144	36	4
144	48	3
144	72	2
144	144	1

$144 /1 = 144$
$144 / 2 = 72$
$144 / 3 = 48$
...
$144 / 8 = 18$
$144 / 9 = 16$
제곱근인 12를 제외한 나머지 절반 약수 16, 18, 24, 36, 48, 72, 144를 알 수 있다.

모든 약수의 중간?

그렇다면 주어진 수의 모든 약수 중에 '중간'은 어떻게 구할까

144의 약수들 중 중간은 9까지인가, 12까지인가, 16까지인가?

위에서도 볼 수 있듯이 주어진 수의 제곱근이 모든 약수의 중간이다.

144라면 12
10이라면 3.162...
20이라면 4.4721...

내용 종합

이렇게 본다면 1~144까지 모든 수에 144를 나누는 것이 아니라
1~12까지만 144를 나누면 모든 약수의 개수를 구할 수 있다.
(물론 약수 자체도 구할 수 있다.)

=> 시간 복잡도가 $O(n)$에서 $O(\sqrt n)$이 된다.

약수의 개수 구하는 코드

1~N까지 계산하는 코드

static void Main(string[] args)
{
    int num = 144;
    int count = 0;

    for(int i=1; i<=num; ++i)
    {
        if(num % i == 0)
        {
            ++count;
        }
    }

    Console.WriteLine(count);
}

1~$\sqrt n$까지 계산하는 코드

static void Main(string[] args)
{
    int num = 144;
    int count = 0;

    for(int i=1; i * i<= num; ++i)
    {
        if (i * i == num)
        {
            ++count;
        }
        else if (num % i == 0)
        {
            count += 2;
        }
        
    }

    Console.WriteLine(count);
}

i의 제곱이 num을 넘어버리면 for문을 탈출한다.
연산의 양이 굉장히 짧아진다.

---

지금은 유니티엔진 & C# 프로그래머로 취직하기 위해 공부중이지만 알고리즘 문제를 풀며 느끼는 것은 수학은 인생의 공부로 생각하고 기초부터 천천히 다시 해봐야겠다는 것이다.

수학 공부는 논리력을 키워주고 문제(수학, 일상 등)를 바라보는 시각이 달라지게 해줄 것이라는 기대감을 가지게 해준다.

진짜로 그러길 바라며 천천히 공부해봐야겠다.