记录编号	465483	评测结果	AAAAAAAATT
题目名称	整数合并	最终得分	80
用户昵称	FFF团	是否通过	未通过
代码语言	C++	运行时间	2.010 s
提交时间	2017-10-27 09:04:06	内存使用	0.94 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int A,B,P,ans;
bool not_prime[100005];
int prime[10005];
int fa[100005];
vector<int>v[10005];
void S_prime(int limit){
	not_prime[0]=not_prime[1]=1;
	for(int i=2;i<=limit;i++){
		if(!not_prime[i])prime[++prime[0]]=i;
		for(int j=1;j<=prime[0]&&i*prime[j]<=limit;j++){
			not_prime[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void init(){
	for(int i=A;i<=B;i++)
	for(int j=1;j<=prime[0]&&prime[j]<=i;j++)
	if(i%prime[j]==0)v[j].push_back(i);
	for(int i=A;i<=B;i++)
	fa[i-A]=i-A;
}
void work(){
	int L=lower_bound(prime+1,prime+prime[0]+1,P)-prime;
	for(int i=L;i<=prime[0];i++){
		int l=v[i].size();
		for(int j=0;j+1<l;j++){
			int f1=find(v[i][j]-A),f2=find(v[i][j+1]-A);
			if(f1!=f2){
				fa[f1]=f2;
			}
		}
	}
}
int main(){
	//freopen("a.in","r",stdin);
	freopen("setb.in","r",stdin);
	freopen("setb.out","w",stdout);
	scanf("%d%d%d",&A,&B,&P);
	
	S_prime(B);
	init();
	work();
	for(int i=A;i<=B;i++)
	if(fa[i-A]==i-A)ans++;
	printf("%d",ans);
	return 0;
}