# Codeforces-Round-400#B-Sherlock and his girlfriend

Sherlock and his girlfriend

time limit per test 1 second memory limit per test 256 megabytes

Sherlock has a new girlfriend (so unlike him!). Valentine’s day is coming and he wants to gift her some jewelry.

He bought n pieces of jewelry. The i-th piece has price equal to i+1, that is, the prices of the jewelry are 2,3,4,… n+1.

Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don’t have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used.

Help Sherlock complete this trivial task.

传送门：CF776B

## Input

The only line contains single integer n (1≤n≤100000) — the number of jewelry pieces.

## Output

The first line of output should contain a single integer k, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints. The next line should consist of n space-separated integers (between 1 and k) that specify the color of each piece in the order of increasing price. If there are multiple ways to color the pieces using k colors, you can output any of them.

## Sample Input

1 | 3 |

## Sample Output

1 | 2 |

## 题解

一开始看错题了尴尬...注意是素因数 那么所有素数可以涂成同一种颜色，而其他的涂另外一种颜色就好了 注意1和2的特判颜色种数## AC code:(不包含输入类)

1 | import java.util.*; |