记录编号	408383	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	Emine	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2017-05-24 15:57:44	内存使用	1.17 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
bool flag[100010]={0};
int prime[100010];
int fa[100010];
int primesize=0;
inline void getprime(){
	flag[0]=flag[1]=1;
	for(int i=2;i<=100000;i++){
		if(!flag[i]){
			prime[++primesize]=i;
		}
		for(int j=1;j<=primesize&&i*prime[j]<=100000;j++){
			flag[i*prime[j]]=1;
			if(i%prime[j]==0)
				break;
		}
	}
}
inline int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
	freopen("setb.in","r",stdin);
	freopen("setb.out","w",stdout);
	int L,R,P;
	scanf("%d %d %d",&L,&R,&P);
	for(int i=L;i<=R;i++)
		fa[i]=i;
	getprime();
	int l=1;
	while(prime[l]<P)
		l++;
	for(int i=l;i<=primesize;i++){
		if(prime[i]>R)
			break;
		int u=L/prime[i];
		u*=prime[i];
		while(u<L)
			u+=prime[i];
		int now=u;
		while(u<=R){
			int ff=find(now),ft=find(u);
			if(ff!=ft)
				fa[ff]=ft;
			u+=prime[i];
		}
	}
	int size=0;
	for(int i=L;i<=R;i++){
		find(i);
		if(fa[i]==i)
			size++;
	}
	printf("%d\n",size);
	//for(int i=L;i<=R;i++)
	//	printf("%d %d\n",i,fa[i]);
return 0;
}