[C++]약수의 개수

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    int n, i, j, cnt = 0;
    int arr[50001];
    
    scanf("%d",&n);
    
    for(i = 1; i <= n; i++){
        for(j = i; j <= n; j = j+i){ //i를 약수로 갖는 숫자들은 i의 배수(i만큼 증가)이다.
                arr[j]++;//i를 약수로 갖는 숫자 j번째 인덱스에 1씩 count한다.
        }
    }
    
    for(i = 1; i <= n; i++){
        printf("%d",arr[i]);
    }
    return 0;
}

성찰

• 역으로 생각하는 방법을 적용한다 : 8의 약수는 무엇일까? => 8을 약수로 갖는 수는 무엇일까? == 8의 배수는 무엇일까?
• 1~i를 약수로 갖는 수를 모두 count한다.
• i를 약수로 갖는 수는 i의 배수이다.(2를 약수로 갖는 수는 2,4,6,8..)