RT

#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int fa[maxn*10],rk[maxn*10],p;
bool pr[maxn*10];
int find(int x)
{
	if(x==fa[x]) return x;
//	int p=find(fa[x]);
//	fa[x]=p;
//	return p;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx==fy) return;
	if(rk[fx]>rk[fy]) fa[fy]=fx;
	else if(rk[fx]<rk[fy]) fa[fx]=fy;
	else fa[fx]=fy,++rk[fy];
}
bool r(int num){
    for(int i=2;i*i<=num;i++){
        if(num%i==0&&i>=p){
            return 1;
        }
    }
    return 0;
}

int main()
{
	int n,m;
	cin>>n>>m>>p;
	int sum=m-n+1;
	for(int i=n;i<=m;i++){
		fa[i]=i,rk[i]=1;
		pr[i]=r(i);
	}
	for(int i=n;i<=m;i++){
		if(pr[i])
			for(int j=n+1;j<=m;j++){
				if(pr[i]){
					if(__gcd(i,j)>=p&&find(fa[i])!=find(fa[j])){
						merge(i,j);
						sum--;
					}
				}
			}
	}
	cout<<sum;
	return 0;
}

估计我的思路不对但是数据过水放我过了