자연수 색칠하기 2

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

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

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

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