자연수 색칠하기 2

면접 대비

시간 제한1초메모리 제한1024 MB

요약

1부터 N까지의 자연수를 칠하되, 서로소가 아닌 두 수의 색이 달라지도록 최소한의 색을 사용하는 문제입니다.

문제

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

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

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

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