题目链接：P1621 集合 - 洛谷 | 计算机科学教育新生态
题目难度：普及/提高
解题思路:这个题要求我们在一个区间[A,B]中找出几个集合,集合中的数满足是一个大于等于P的质因数的个数,我们想到了并查集来维护这个集合，初始时候每个数的父亲就是本身，我们明确了求解答案的条件，就是将所有有大于等于P的质因数的一堆数合并起来，统计父亲是自己的个数，我们可以用筛法来求，将所有公共质因数的数在筛法过程中直接合并。最后输出答案即可。
下面奉上代码部分：
#include<bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=(a); i<(b); i++)
#define _rep(i,a,b) for(int i=(a); i<=(b); i++)
typedef long long ll;
const int N = 1e5 + 10;
bool prime[N];
int f[N];
int a,b,p;int find(int x)
{if(f[x] != x) f[x] = find(f[x]);return f[x];
} int get_prime()//埃氏筛
{int ans = b - a + 1;//将答案初始化为a~b间数的个数，每合并一次减1就可以了for(int i=2; i<=b; i++){if(!prime[i]){if(i >= p){for(int j = i * 2; j <= b; j += i){prime[j] = true;if(j - i>=a && find(j) != find(j-i))//将当前被筛的数与上一个被筛的数合并（第一个被筛的数和质因数本身合并）//注意这两个数都要在a~b之间才合并{f[find(j)]=find(j-i);//合并集合 ans--;}}}else{for(int j = i*2; j <= b; j += i){prime[j]=true;}}} }return ans;
}int read()//快读函数
{int k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(nullptr),cout.tie(nullptr);a= read(),b = read(),p = read();int ans = b - a + 1;_rep(i,a,b) f[i] = i;cout<< get_prime()<<'\n';return 0;
}
