효율적인 약수의 개수를 찾는 알고리즘

BOJ 13225번 Divisors : http://hsdevelopment.tistory.com/109

BOJ 13226번 Divisors Again : http://hsdevelopment.tistory.com/108

10,000,000 이하의 자연수에 대한 약수의 '개수'를 찾는 알고리즘.

#define MAX 10000000
 
int Divisors[MAX + 1] = { 0, };
 
void getFactorsBrute()
{
    memset(Divisors, 0, sizeof(Divisors));
 
    for (int i = 1; i <= MAX; i++)
    {
        for (int j = i; j <= MAX; j += i)
        {
            ++Divisors[j];
        }
    }
}

13
Divisors[1] = 1
Divisors[2] = 2
Divisors[3] = 2
Divisors[4] = 3
Divisors[5] = 2
Divisors[6] = 4
Divisors[7] = 2
Divisors[8] = 4
Divisors[9] = 3
Divisors[10] = 4
Divisors[11] = 2
Divisors[12] = 6
Divisors[13] = 2