2553269_tle.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

char k[101];
int l;
int prime[1000001];

void init()
{
	int i, j;

	memset(prime,0,sizeof(prime));
	for(i = 2; i < 1000001; i++)
	{
		if(prime[i]==0)
		{
			for(j = 2*i; j < 1000001; j+=i)
				prime[j] = 1;
		}
	}
	int num = 0;
	for(i = 2; i < 1000001; i++)
		if(!prime[i])
			prime[num++] = i;
	prime[num] = 100000000;
}

int div(int n)
{
	int i, t;

	t = 0;
	for(i = 0; k[i]!='\0'; i++)
	{
		t += (k[i]-'0');
		if(t>=n)
			t = t-t/n*n;
		t *= 10;
	}
	return t==0;
}

int main()
{
	int i;

	//freopen("a.txt","r",stdin);
	//freopen("b.txt","w",stdout);
	init();
	while(scanf("%s%d",k,&l)==2)
	{
		if(!l)
			break;
		for(i = 0; prime[i] < l; i++)
		{
			if(div(prime[i]))
			{
				printf("BAD %d\n",prime[i]);
				goto con;
			}
		}
		printf("GOOD\n");
con:
		;
	}
	return 0;
}