集合

现在给你一些连续的整数，它们是从A到B的整数。一开始每个整数都属于各自的集合，然后你需要进行一下的操作：

每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于P的公共质因数，那么把它们所在的集合合并。

反复如上操作，直到没有可以合并的集合为止。

现在Caima想知道，最后有多少个集合。

先线性筛一遍
找出大于P质数，找到它在[a,b]间倍数，合并

#include<bits/stdc++.h>
#define re return
#define ll long long
#define inc(i,l,r) for(int i=l;i<=r;++i)
#define dec(i,l,r) for(int i=l;i>=r;--i)
const int maxn=10e5+5;
using namespace std;
template<typename T>inline void rd(T&x)
{
	char c;bool f=0;
	while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
	x=c^48;
	while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
	if(f)x=-x;
}

int n,prime[maxn],ans,notprime[maxn],fa[maxn],a,b,p,cnt;
inline int find(int x)
{
re x==fa[x]?x:fa[x]=find(fa[x]);
}

inline void Get_prime()
{

	notprime[1]=1;
	inc(i,1,b)
	{
	    if(!notprime[i])prime[++cnt]=i;
    	for(int j=1;j<=cnt&&prime[j]*i<=b;++j)
    	{
       	 notprime[prime[j]*i]=1;
       	 if(i%prime[j]==0)break;
    	}
	}
}

int main()
{
	scanf("%d%d%d",&a,&b,&p);
	Get_prime();
	ans=b-a+1;
	inc(i,a,b)fa[i]=i;
	inc(i,1,cnt)
	if(prime[i]>=p)
	{
		int last=0;
		for(int j=prime[i];j<=b;j+=prime[i])
		if(j>=a)
		{
			if(last)
			{
				int f1=find(last),f2=find(j);
				if(f1!=f2)
				{
					fa[f1]=f2;
					--ans;
				}	
			}
			last=j;
		}
	}
printf("%d",ans);
re 0;
}