记录编号	48264	评测结果	AAAAAAAATT
题目名称	整数合并	最终得分	80
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	2.579 s
提交时间	2012-11-05 12:43:54	内存使用	2.38 MiB

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=100010;
int A,B,P,Num[MAXN],prime[10001],top=0;

int find(int k)
{return ((k==Num[k])?k:(Num[k]=find(Num[k])));}
inline void merge(int a,int b){Num[b]=a;}

inline void makeprime()
{
	prime[++top]=2;
	for(int i=3;i<=10000;i+=2)
	{
		bool flag=1;
		for(int j=2;j*j<=i;j++)
		{
			if(i%j) continue;
			flag=0;break;
		}
		if(flag) prime[++top]=i;
	}
}

int main()
{
	freopen("setb.in","r",stdin);
	freopen("setb.out","w",stdout);
	scanf("%d %d %d\n",&A,&B,&P);
	int x,y,flag; makeprime();
	for(int i=A;i<=B;i++) Num[i]=i;
	for(int i=A;i<=B;i++)
	{
		for(int j=i+1;j<=B;j++)
		{
			x=find(i),y=find(j);
			if(x==y) continue;flag=0;
			for(int k=1;prime[k]<=i;k++)
			{
				if(prime[k]<P) continue;
				if(prime[k]>i) break;
				if(i%prime[k]) continue;
				if(j%prime[k]) continue;
				flag=1; break;
			}
			if(flag) merge(x,y);
		}
	}int ans=0;
	for(int i=A;i<=B;i++)
		if(Num[i]==i) ans++;
	printf("%d\n",ans);
	return 0;
}