记录编号	48281	评测结果	WAAWWWAWTT
题目名称	整数合并	最终得分	30
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	2.824 s
提交时间	2012-11-05 14:21:02	内存使用	18.82 MiB

#include <fstream>
using namespace std;
ifstream cin("setb.in");
ofstream cout("setb.out");
int f[2001][2001],a,b,p,lon[20001];
bool zs[100000],cz[100000];
void zhishu()
{
	int i,j;bool f;
	for (i=0;i<=b;i++) {zs[i]=false;cz[i]=true;}
	zs[2]=true;zs[3]=true;
	for (i=5;i<=b;i++)
	{
		f=true;
		for (j=2;j<=i/2;j++)
			if (i%j==0) f=false;
		if (f) zs[i]=true;
	}
}
void init()
{
	int i;
	for (i=1;i<=b-a+1;i++) {f[i][1]=a+i-1;lon[i]=1;}
}
bool keyi(int x,int y)
{
	int i;
	for (i=p;i<=x/2;i++)
	{
		if (x%i==0&&zs[i])
			if (y%i==0) return true;
	}
	return false;
}
void hebing(int x,int y)
{
	int i;
	for (i=1;i<=lon[y];i++)
		f[x][i+lon[x]]=f[y][i];
}
int main()
{
	int i,j,k,l,ans=0;
	cin>>a>>b>>p;
	zhishu();
	init();
	for (i=1;i<=b-a+1;i++)
	{
		if (cz[i])
		{
			for (j=1;j<=lon[i];j++)
				for (k=i+1;k<=b-a+1;k++)
					if (cz[k])
						for (l=1;l<=lon[k];l++)
							if (keyi(f[i][j],f[k][l]))
							{
								cz[k]=false;
								hebing(i,k);
								lon[i]+=lon[k];
								break;
							}
		}
	}
	for (i=1;i<=b-a+1;i++)
		if (cz[i]) ans++;
	cout<<ans<<endl;
	return 0;
}