题目
思路
并查集+埃氏筛，一开始连通块的个数是(b-a+1)个，在筛素数的过程中只要当前素数大于(p)就对该素数筛出来的数进行判断，如果不连通并且小的数大于等于(a)就合并连通块个数减一，最后的联通块个数就是答案。（具体看代码）
(Code)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define MAXN 100001
using namespace std;
int ans,a,b,p;
int fa[MAXN],size[MAXN];
bool prime[MAXN];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void Union(int x,int y){
int rootx=find(x),rooty=find(y);
if(rootx==rooty) return;
if(size[rootx]>size[rooty]){
fa[rooty]=rootx;
size[rootx]+=size[rooty];
}else{
fa[rootx]=rooty;
size[rooty]+=size[rootx];
}
}
inline void read(int &T){
int x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
int main(){
read(a),read(b),read(p);
for(int i=a;i<=b;++i){
fa[i]=i;
}
ans=b-a+1;
for(int i=2;i<=b;++i){
if(!prime[i]){
if(i>=p){//如果当前质数大于p才合并
for(int j=i*2;j<=b;j+=i){
if(j-i>=a&&find(j)!=find(j-i)){//将当前被筛的数与上一个被筛的数合并（第一个被筛的数和质因数本身合并），注意这两个数都要在a~b之间才合并
Union(j,j-i);
ans--;
}
prime[j]=1;
}
}else{
for(int j=i*2;j<=b;j+=i){
prime[j]=1;
}
}
}
}
printf("%d
",ans);
return 0;
}