题目
Caima给你了所有[a,b]范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数，如果这两个整数拥有大于等于p的公共质因数，那么把它们所在的集合合并。
重复如上操作，直到没有可以合并的集合为止。
现在Caima想知道，最后有多少个集合。
输入输出格式
输入格式
一行，共三个整数a,b,p，用空格隔开。
输出格式
一个数，表示最终集合的个数。
输入输出样例
输入样例
10 20 3输出样例
7解析
针对这个题目，使用并查集+线性筛解决。
首先从p开始，枚举所有不大于b的质数t，然后枚举所有以t作为因数的小于b的数（标记这些数，如果再遇到，则跳过），接着将这些数所在的集合进行合并，最后统计总共存在多少集合。
#include<iostream>
#include<cmath>
using namespace std;
int a,b,p,ans,f[100005],mark[100005],vis[100005];
bool judge(int x){//判断是否为质数
if(x==2){
return true;
}
if(x%2==0){
return false;
}
for(int i=3;i<=sqrt(x);i+=2){
if(x%i==0){
return false;
}
}
return true;
}
int find(int x){//查找
if(x!=f[x]){
f[x]=find(f[x]);
}
return f[x];
}
int main(){
cin>>a>>b>>p;
for(int i=1;i<=b;i++){
f[i]=i;
}
for(int i=p;i<=b;i++){
if(mark[i]==1){
continue;
}
if(judge(i)){
mark[i]=1;
for(int j=2;j*i<=b;j++){//相应质数的因子进行筛选
mark[j*i]=1;
if(j*i<a){
continue;
}
int t1=find(i),t2=find(j*i);//合并
if(t1!=t2){
f[t1]=t2;
}
}
}
}
for(int i=a;i<=b;i++){//最后统计
if(!vis[find(i)]){
ans++;
vis[find(i)]=1;
}
}
cout<<ans;
return 0;
}