记录编号	601984	评测结果	AAAAAAAAAA
题目名称	487.整数合并	最终得分	100
用户昵称	梧叶已同秋雨去	是否通过	通过
代码语言	C++	运行时间	0.248 s
提交时间	2025-06-29 20:30:07	内存使用	3.96 MiB

#include<bits/stdc++.h>
using namespace std;
int a,b,p,sum,z[100005],cnt,n;
int c[100005],bb[100005];
int zhi(int a){
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			return 0;
		} 
	}return 1;
}
void yu(){
	cnt=0;
	for(int i=p;i<=b;i++){
		if(zhi(i)){
			z[++cnt]=i;
		}
	}
}
int main(){
//	freopen("setb.in","r",stdin);
//	freopen("setb.out","w",stdout);
	scanf("%d%d%d",&a,&b,&p);
	yu();
	for(int i=1;i<=cnt;i++){
		int j=a/z[i];
		while(z[i]*j<=b){
			if(a<=z[i]*j&&z[i]*j<=b){
				if(c[z[i]*j]==0&&bb[z[i]]==0){
					bb[z[i]]=2;
				}
//				cout<<bb[z[i]]<<" "<<z[i]<<" "<<j<<" "<<z[i]*j<<endl;
				c[z[i]*j]=1;
				if(zhi(j)==1&&j>=p&&z[i]!=j){
					bb[j]=1;
//					cout<<"出现："<<j<<endl;
				}else if(zhi(j)==0){
					for(int k=1;z[k]<=j;k++){
						if(j%z[k]==0&&z[k]!=z[i]){
							bb[z[k]]=1;
						}
					}
				}
			}
			j++;
		}
		//cout<<z[i]<<" "<<bb[z[i]]<<endl;
		if(bb[z[i]]==2){
			bb[z[i]]=1;
			sum++;
		}
	}
	for(int i=a;i<=b;i++){
		if(c[i]==0){
			sum++;
//			cout<<"没："<<i<<"\n";
		}
	}
	cout<<sum;
	return 0;
}