记录编号	601937	评测结果	AAAAAAAAAA
题目名称	487.整数合并	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2025-06-29 17:41:23	内存使用	4.80 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a,b,p,ans;
ll f[100020],pm[100020],vis[100020],cnt;

int get(int x){
    if(f[x]==x) return x;
    else return f[x]=get(f[x]);;
}

void merge(int x,int y){
    int t1=get(x),t2=get(y);
    if(t1!=t2){
        f[t2]=t1;
    }
    return;
}

void make(){
    memset(pm,1,sizeof(pm));
    ll k=sqrt(b);
    pm[0]=0;
	pm[1]=0;
    for(int i=2;i<=k;i++)
        if(pm[i])
            for(int j=2*i;j<100010;j+=i) pm[j]=0;
}

int main(){
	freopen("setb.in","r",stdin);
	freopen("setb.out","w",stdout);
	scanf("%lld %lld %lld",&a,&b,&p);
	for (int i=a;i<=b;i++){
		f[i]=i;
	}
	make();
	for (int i=p;i<=b;i++){
		if (pm[i]) vis[++cnt]=i;
	}
	for(int i=1;i<=cnt;i++){
        ll cc=0;
        while(cc*vis[i]<a) cc++;
        while(vis[i]*(cc+1)<=b){
            merge(vis[i]*cc,vis[i]*(cc+1));
            cc++;
        }
    }
    for(int i=a;i<=b;i++)
        if(f[i]==i) ans++;
    printf("%lld",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}