모두의 약수

모두의 약수 (제한시간 1초)

입력

자연 수 N(5<=N<=50,000)

출력

1부터 N까지의 약수의 개수

처음에는 이중반복문으로 하나씩 약수인지 판별하려고 했지만 타임아웃 발생

i는 1부터 N까지 증가하면서 i를 약수로 가지고 있는 숫자들의 개수 증가시키기

#include <iostream>
int arr[50001]={0,};
using namespace std;

int main() {
    int num;
    cin>>num;
    
    for(int i=1;i<=num;i++){
        for(int j=i;j<=num;j+=i){
            arr[j]++;
        }
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

결과

8
1 2 2 3 2 4 2 4