E. Rasta Thamaye Dilo

链接：[https://codeforces.com/gym/104679/problem/E?adcd1e=caf4fedm9escdm&csrf_token=062b3628aaa43205c694e16f77dbe6ec]
题意：
村庄=点
路=点与点的连线
1.有t组数据，每组给一个数字n，问可以从一点走到任意一点需要建的最小路数。
2.i和j之间可以整除，则i，j之间已经有路。

题解：根据2.找从2~n有几个不连通的堆。

• 两个质数堆会由他们的公倍数连成一堆，质数会与其倍数连成一堆，其中有交叉，最早的交叉出现在2倍时。
• 2*n是2与n的公倍数，这说明2和前n个数（包括n）连成一堆，即前n个质数为一堆。
  ans=总质数-前n质数连成一堆；

故解题流程为
1.埃氏筛选法记录质数
2.前缀和记录前n个质数个数
3.prefix[n]-prefix[n/2]即为要建立的最小数

特判:当n=2时，只有一个点，不需要路，ans=0；
当n=3时，只有两个质数用一条线连接即可
`#include

include

using namespace std;
const int M = 1e7;
int main()
{
vectorprime(M + 1, 1);
prime[0] = 0, prime[1] = 0;
for (int i = 2;i <= M;i++) {
if (prime[i]) {
for (int j = 2 * i;j <= M;j+=i) {
prime[j] = 0;
}
}
}
for (int i = 1;i <= M;i++) {
prime[i] += prime[i - 1];
}
cout << prime[6];
int t;
cin >> t;
while (t--) {
int m;
cin >> m;
if (m <= 3) cout << m - 2 << endl;
else
cout << prime[m] - prime[m / 2] << endl;
}
return 0;
}`