2553136_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 div(int n)
{
	int i, t;

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

int main()
{
	int i;

	init();
	while(scanf("%s%d",k,&l)==2)
	{
		if(!l)
			break;
		for(i = 2; i < l; i++)
		{
			if(!prime[i]&&div(i))
			{
				printf("BAD %d\n",i);
				goto con;
			}
		}
		printf("GOOD\n");
con:
		;
	}
	return 0;
}