记录编号	472119	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	Continue	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2017-11-07 11:34:46	内存使用	1.11 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxp=10000+5;
const int maxn=100000+5;

int not_pri[maxn],pri[maxp],pcnt;

void init(int n) {
	not_pri[0]=not_pri[1]=1;
	for(int i=2;i<=n;i++) {
		if(!not_pri[i]) pri[pcnt++]=i;
		for(int j=0;j<pcnt&&1ll*i*pri[j]<=n;j++) {
			not_pri[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}

int fa[maxn];

int find(int x) {
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

void merge(int x,int y) {
	fa[find(x)]=find(y);
}

int main() {
	freopen("setb.in","r",stdin);
	freopen("setb.out","w",stdout);
	
	int A,B,P;
	scanf("%d%d%d",&A,&B,&P);
	init(B);
	
	for(int i=A;i<=B;i++) fa[i]=i;
	for(int i=0;i<pcnt;i++) if(pri[i]>=P) {
		int j=(A/pri[i]+(A%pri[i]!=0))*pri[i];
		for(;j+pri[i]<=B;j+=pri[i]) merge(j,j+pri[i]);
	}
	
	int ans=0;
	for(int i=A;i<=B;i++) ans+=(i==fa[i]);
	printf("%d\n",ans);
	return 0;
}