9. 모두의 약수 ***

문제설명

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에 자연수 N이 주어진다.
8

출력설명

첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다.
1 2 2 3 2 4 2 4

시간복잡도 O(N^2) 코드

#include <iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= i; j++)
		{
			if (i % j == 0)
				cnt++;
		}
		cout << cnt << " ";
	}
}

#include <iostream>
using namespace std;

int cnt[50001];
int main() 
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j = j + i)
			cnt[j]++;
	}
	for (int i=1;i<=n;i++)
		cout << cnt[i] << " ";
}

다시 보면 좋을 것 같다