숫자만 추출


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

만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다.

출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.

1 2 2 3 2 4 2 4 와 같이 출력한다.

▣ 입력설명
첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.

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

▣ 입력예제 1 
8
 
▣ 출력예제 1
1 2 2 3 2 4 2 4


풀이

일반적으로 쉽게 생각한다면 타임 리미트가 발생한다.
하나하나의 약수를 구하는 것이 아니라 i는 1부터 n까지 될 되, i가 약수인 수에다가 약수 값을 증가시키는 방법으로 해결하면 된다.

코드를 보면 좀 더 쉽게 이해가 가능하다.

vector<int> vec;

void solve()
{
	int n;
	cin >> n;
	vec = vector<int>(n + 1, 0);

	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; j = j + i)
		{
			vec[j]++;
		}
	}

	for (int i = 1; i <= n; ++i)
		cout << vec[i] << " ";
}

전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> vec;

void solve()
{
	int n;
	cin >> n;
	vec = vector<int>(n + 1, 0);

	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; j = j + i)
		{
			vec[j]++;
		}
	}

	for (int i = 1; i <= n; ++i)
		cout << vec[i] << " ";
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고