You‘re given an integer nn. For every integer ii from 22 to nn, assign a positive integer aiai such that the following conditions hold:
A pair of integers is called coprime if their greatest common divisor is 11.
筛法，把下标为素数的赋予新值，他的倍数再赋予同样的值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
int n, m, k, t;
int a[MAXN];
int main()
{
cin >> n;
int cnt = 0, pos = 0;
for (int i = 2;i <= n;i++)
{
if (a[i] != 0)
continue;
// cout << i << endl;
a[i] = ++pos;
cnt++;
int j = 2*i;
while (j <= n)
{
a[j] = pos;
j += i;
cnt++;
}
// if (cnt >= n-1)
// break;
}
for (int i = 2;i <= n;i++)
cout << a[i] << ‘ ‘ ;
cout << endl;
return 0;
}
C. Ehab and a Special Coloring Problem
原文：https://www.cnblogs.com/YDDDD/p/10972867.html