[알고리즘] 모두의 약수

문제 내용

• 자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하 세요.
• 만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다.
• 출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.
• 8 -> 1 2 2 3 2 4 2 4

입출력

• 첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.
• 첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다.

구현 방식

• 맨처음에 간단하게 생각할 수 있는 방식은 1 -> N 까지 하나하나 다 약수를 구하는데, 하나의 수의 약수를 구할때 for 문을 돌면서 i % j == 0 것을 카운트 하는 것이다.
• 해당 문제는 자연수가 50000 까지 가므로 O(n^2) 방식으로 가면, 최대 연산량이 10^9 제곱까지 가버려서 1초가 넘게된다.
  • 10^9 –> 1억 –> 1초
  • 2^30 –> 약 1억 –> 1초
• 생각을 바꿔서, i 를 배수를 가지는 숫자의 약수를 늘려주는 방식으로 진행한다.

vector<int> counter;

void solution(int input ){
    counter = vector<int>(input + 1, 0);
    for (int i = 1; i <= input; i++)
    {
        for (int j = i; j <= input; j = j + i)
        {
            counter[j]++;
        }
    }

    for (int i = 1; i <= input; i++)
        cout << counter[i] << " ";
}