23048번 - 자연수 색칠하기 스페셜 저지

$1$부터 $N$까지의 자연수를 색칠한다. 단, 서로소인 서로 다른 두 자연수는 다른 색으로 칠해야 한다. 최소한의 색을 써서 모든 자연수를 칠하는 방법을 찾는 프로그램을 작성하자.

첫째 줄에 자연수 $N$이 주어진다. ($1 \le N \le 500\,000$)

첫째 줄에 사용한 색의 수 $K$를 출력한다.

둘째 줄에 $N$개의 수를 공백을 사이에 두고 출력한다. $i$번째 수는 자연수 $i$의 색이다. 색은 $1$ 이상 $K$ 이하의 정수로 나타낸다.

다음은 $N=5$일 때의 올바른 색칠과 올바르지 않은 색칠의 예시다.

첫 번째 색칠은 올바른 색칠이다. $2$와 $4$는 같은 색으로 색칠했지만, 서로소가 아니므로 문제의 조건에 위배되지 않는다. 또한, $5$까지의 자연수를 색칠하기 위해 최소 $4$개의 색이 필요함을 증명할 수 있다.

두 번째 색칠은 서로소인 $2$와 $3$이 같은 색으로 칠해졌기 때문에 올바르지 않은 색칠이다.

세 번째 색칠은 최소한의 색깔로 칠하지 않았기 때문에 올바르지 않은 색칠이다.