rt，代码如下：

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#pragma G++ optimize(3)
using namespace std;
int fa[100010],a,b,p,ans=0;
bool bj[100010]={0},bb[100010]={0};
int prime[20010];
int init()
{
	for(int i=1;i<=100001;i++)fa[i]=i;
}
int _find(int aa)
{
	if(aa!=fa[aa])
	{
		fa[aa]=_find(fa[aa]);
	}
	return fa[aa];
}
void ex()
{
	for(int i=2;i<=sqrt(b);i++)
	{
		if(bj[i]==0)
		{
			for(int j=2;i*j<=b+1;j++)
			bj[i*j]=1;
		}
	}
	for(int i=p;i<=b;i++)
	{
		if(bj[i]==0)
		{
			int q=i,h=i+i;
			while(h<=b)
			{
				fa[q]=h;
				q=h;
				h+=i;
			}
			fa[q]=q;
		}
	}
} 
int main ()
{
	cin>>a>>b>>p;
	ex();
	for(int i=a;i<=b;i++)
	{
		int f=_find(i);
		
		if(bb[f]==0)
		{
			bb[f]=1;
			ans+=1;
		}
	}
	cout<<ans;
    return 0;
}

悬赏关注