Codeforces Round #400 (Div. 1 + Div. 2, combined) B. Sherlock and his girlfriend 素数筛法+贪心

My Solution

题意：给出一个n，表示有2、3、......n+1这n个数，要求给这些数涂色，如果一个数是另一个数的质因数则必须涂不同的颜色。

素数筛法+贪心

首先其实只有2种数，一种是素数，一种是以这个素数作为其其中一个因数的数，所以最多用2中颜色。

用素数的O(nlogn)的筛法，边筛素数边涂色，如果i是素数，则涂1，然后对于i*j，(i*j<= n+1)涂上2.，并标记为非素数。

复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const LL MAXN = 1e5 + 8;

LL v[MAXN];
bool f[MAXN];

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("b.out", "w", stdout);
    LL T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    memset(f,  true, sizeof f);
    LL n, k = 1, i, j, ptr;
    cin >> n;
    for(i = 2; i <= n + 1; i++){
        ptr = 1;
        if(f[i]){
            v[i] = ptr;

            for(j = i * i; j <= n + 1; j += i){
                f[j] = false;
                if(!v[j]) {ptr = 2; v[j] = ptr;}
            }
            k = max(k, ptr);
        }
    }
    cout << k << "n" << v[2];
    for(i = 3; i <= n + 1; i++) cout << " " << v[i];


    #ifdef LOCAL
    memset(v, 0, sizeof v);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}