1부터 n까지 약수의 개수 구하기

• 특정 숫자 n의 약수의 개수를 구하는게 아닌 1부터 n까지의 숫자들의 약수 개수를 통으로 구하는 효율적인 방법이다.
• v의 사이즈를 limit+1로 한 이유는 특별한 이유 없이 편의상 i번째 원소에 접근하기 쉽게 하려고 했다.

n	1	2	3	4	5	6	7	8	9	10
개수	1	2	2	3	2	4	2	4	3	4
약수	{1}	{1,2}	{1,3}	{1,2,4}	{1,5}	{1,2,3,6}	{1,7}	{1,2,4,8}	{1,3,9}	{1,2,5,10}

• 위와같이 1부터 10까지 약수의 개수와 약수를 나타내는 표가 있다.
• 자세히 보면 패턴이 있는데 n까지의 각 숫자의 배수에 각 숫자의 약수로 더해주면 약수의 개수가 나온다.

#include <iostream>
#include <vector>

using namespace std;

int main() {

    /**
     * Program that making a list that contains numbers of divisors.
     */

    int limit = 20;
    vector<int> v(limit+1);
    for(int i=1;i<=limit;i++) {
        for(int j=i;j<=limit;j+=i) {
            v[j]++;
        }
    }

    for(int i=1;i<v.size();i++) {
        cout<<i<<": "<<v[i]<<endl;
    }

    return 0;
}

🔽Output🔽

1: 1
2: 2
3: 2
4: 3
5: 2
6: 4
7: 2
8: 4
9: 3
10: 4
11: 2
12: 6
13: 2
14: 4
15: 4
16: 5
17: 2
18: 6
19: 2
20: 6

Github

• https://github.com/kon6443/Algorithms/blob/main/Algorithm/Divisor/divisorList.cpp