算法分析

• 1、一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同，则等价于每一个合数与它的每一个质因子的颜色均不同，等价于质数和合数染的颜色一定不同，因此质数和合数形成了一个二分图，最多只会染两种颜色，当第n件宝贝的价值是n + 1 >= 4时，则表示有两种颜色，否则只有一种颜色
• 2、通过线性筛法把所有的质数筛出来，将所有的质数染成1的颜色，合数染色2的颜色

时间复杂度 $O(n)$

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[] primes = new int[N];
    static int cnt = 0;
    static boolean[] st = new boolean[N];
    static void init(int n)
    {
        for(int i = 2;i <= n;i ++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0;primes[j] * i <= n;j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        init(n + 1);

        if(n + 1 >= 4) System.out.println("2");
        else System.out.println("1");

        for(int i = 2;i <= n + 1;i ++)
        {
            if(!st[i]) System.out.print("1 ");
            else System.out.print("2 ");
        }
    }
}