记录编号	381041	评测结果	AAAAAAAAAA
题目名称	整数合并	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2017-03-10 19:37:49	内存使用	2.79 MiB

//\
487.整数合并\
g++ -g 487.整数合并.cpp -O2 -D LOCAL -D debug


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define is_num(tmp) (tmp<='9' and tmp>='0')
inline int in(void){
	char tmp = getchar();
	int res = 0, f = 1;
	while(! is_num(tmp)) tmp = getchar();
	if(tmp == '-') f = -1, tmp = getchar();
	while(is_num(tmp))
		res = (res << 1) + (res << 3) + (tmp ^ 48),
		tmp = getchar();
	return res * f;
}
#define MAXN 200010
bool unionn(int a,int b);
int Find(int i);
void Get_prime(void);
int biao[MAXN],n,N;
bool prime[MAXN];
int father[MAXN];
int s[MAXN];
int L, R, P;
int main(){
#ifndef LOCAL
	freopen("setb.in", "r", stdin);
	freopen("setb.out", "w", stdout);
#endif
	L=in(),R=in(),P=in();
	for(int i=1;i<=R;++i){
		father[i]=i;
	}
	N=R-L+1;
	prime[0]=prime[1]=true;
	for(int i=2;i*i<=R;++i){
		if(!prime[i]){
			for(int j=i*i;j<=R;j+=i){
				prime[j]=true;
			}
		}
	}
	for(int i=2;i<=R;++i){
		if(!prime[i])biao[n++]=i;
	}/*
	for(int i=0;i<n;++i){
		printf("%d ",biao[i]);
	}*/
	
	for(int i=0;i<n;++i){
		if(biao[i]<P)continue;
		int now(biao[i]),next;
		while(now<L)now+=biao[i];
		next=now+biao[i];
		while(next<=R){
			if(unionn(now,next))--N;
			now=next;
			next=now+biao[i];
		}
	}
	printf("%d",N);
	return 0;
}
bool unionn(int a,int b){
	int ii=Find(a),jj=Find(b);
	if(ii==jj)return false;
	else father[ii]=jj;
	return true;
}
int Find(int x)
{
    int k,j,r;
    r=x;
    while(r!=father[r])     //查找根节点
        r=father[r];      //找到根节点，用r记录下
    k=x;        
    while(k!=r)             //非递归路径压缩操作
    {
        j=father[k];         //用j暂存father[k]的父节点
        father[k]=r;        //father[x]指向跟节点
        k=j;                    //k移到父节点
    }
    return r;         //返回根节点的值            
}