[C++] 모두의 약수

📄문제

자연수 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)가 주어진다.

8

⬆️ 출력

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

1 2 2 3 2 4 2 4

 

📝 풀이

• 첫 번째 풀이는 가장 단순하고, 직관적인 방법으로 해결하였습니다.

#include <iostream>

int main()
{
	int primes[50001] = { 0, };
	int N;

	scanf_s("%d", &N);

	for (int i = 1; i <= N; ++i)
		for (int j = i; j <= N; j += i)
			++primes[j];

	for (int i = 1; i <= N; ++i)
		printf("%d ", primes[i]);
}

• 일반적인 방법으로 1부터 n까지 1씩 증가하여 %를 통해 약수를 구하는 방법은 느릴것으로 판단하였습니다.
• 배열을 통해 첫 값에 배수에 해당하는 모든 배열의 값을 1씩 증가시키는 방법을 사용하였습니다.