线性筛法

最多两种分法的二分图 质数为一类 合数为一类 （无关之间的变量永远不会相连）

写法就是y总的写法，这里求素数的时候为了练习欧拉函数和最小质因子就加了minp和phi数组

python版本

def getPrimes(n):
    phi[1] = 1
    for i in range(2,n+1):
        if vis[i] == False:
            primes.append(i)
            phi[i] = i - 1
            minp[i] = i
        j = 0
        while primes[j]*i <= n :
            vis[primes[j]*i] = True
            phi[primes[j]*i] = (primes[j] - 1)*phi[i]
            minp[primes[j]*i] = primes[j]
            if i % primes[j] == 0:
                phi[primes[j]*i] = primes[j]*phi[i]
                break
            j += 1

n = int(input())
n += 1

vis= [False]*(n + 1)
phi = [0]*(n + 1)
minp = [0]*(n + 1)
primes = []
getPrimes(n)


res = [int(i) + 1 for i in vis[2:]]

if n <= 3:
    print(1)
else:
    print(2)
print(' '.join(map(str,res)))