#include<iostream>
using namespace std;
const int MAX=1000001;
int prime[MAX];
bool is[MAX];
int getprime()
{
	memset(is,true,sizeof(is));
	int i,j,k;
	k=0;
	prime[k++]=2;
	for(i=3;i<MAX;i++)
	{
		if(is[i])
		{
			prime[k++]=i;
		}
		for(j=0;j<k && prime[j]*i<MAX;j++)
		{
			is[prime[j]*i]=false;
			if(i%prime[j]==0)
				break;
		}
	}
	return k;
}
int main()
{
	int m=getprime();
	char str[102];
	int l,len,i,j,sum;
	while(scanf("%s%d",str,&l))
	{
		if(str[0]=='0' && l==0)break;
		len=strlen(str);
		for(i=0;prime[i]<l && i<m;i++)
		{
			sum=0;
			for(j=0;j<len;j++)
			{
				sum*=10;
				sum+=str[j]-'0';
				sum%=prime[i];
			}
			if(sum==0)
			{
				break;
			}
		}
		if(prime[i]>=l || i>=m)
		{
			printf("GOOD\n");
		}
		else
		{
			printf("BAD %d\n",prime[i]);
		}
	}
	return 0;
}

• Re:超时，大牛们给瞧瞧，线性打了个素数表，但是还是过不去，help！！！ (67) 455462586 2011-11-08 10:47:39
  • Re:超时，大牛们给瞧瞧，线性打了个素数表，但是还是过不去，help！！！ (81) xieweibbz 2012-03-27 16:32:13