백준 - 23048번 : 자연수 색칠하기 (C++)

풀이 방법 : 에라토스테네스의 체

1부터 N까지 숫자를 색칠하되, 서로소인 다른 자연수는 다른 색으로 칠해야하는 문제

결국 ( 1 < i ) 라 할때 i의 배수는 i와 같은 색으로 칠할 수 있다는 얘기다.

1은 무조건 다른 모든 숫자와 다른 색이어야하므로 2부터 시작해서 소수들의 N이하인 배수들을 다 같은 색깔로 색칠해주면 되는 문제다.

#include <iostream>
#include <vector>

using namespace std;

int Color[500001] = {};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	Color[1] = 1;
	int ColorCnt = 1;

	for (int i = 2; i <= N; ++i)
	{
		int Num = i;
		
		if (Color[i] != 0)
			continue;

		++ColorCnt;

		while (Num <= N)
		{
			Color[Num] = ColorCnt;
			Num += i;
		}
	}

	cout << ColorCnt << '\n';
	for (int i = 1; i <= N; ++i)
	{
		cout << Color[i] << ' ';
	}

}