学步园

题目连接

这题不知wA多小次了，先是打素数表超时，后是取余数超时。

没法，在绝望的情况下看了大牛的，我无语了。。。。。

题意：（英语基础不行，题意都很坑爹）。

给你一个数，它是由两个素数相乘而得的，再给你一个数M，如果其中有一个素数小于该数M，就输出“BAD”，并且要输出该素数。只有两个素数都它大于这数M，才输出“GOOD”。

（这题目废话真多！，何必呢？）

分析题目：

 一看到素数，就想到了打素数表，这是解决这题的第一步，但怎样快速呢，又是一个麻烦事。另外，平时我们用的数都是十进制的数。所以，这题就要坑你，人是活的，想想看，

为什么又二进制，八进制，十六进制。还不是处理方便些。计算机有点笨，它只认识1和0,如果数字很大我们这样处理呢，既然有这么多进制，并且他有规律，就是处理为位。比如

十六进制中字母可以代表两位数，100进制代表三位数。如果1000进制，那它一位可代表四位数了。记住，这就有点像数小数点，一千是数三位的。它本身要保留一位，这可

别搞错了。

素数筛选：

一个合数都至少含有一个素因子。这是素数筛选的思路。比如 30=2*3*5，它含有三个，我们只要用2去筛选就行了，没必要用3和5再去筛选。所以它筛选的速度比较快

记住：不能用老土的方法去筛选，会TLE的。
同余定理：
比如：(a+b)%c=(a%c+b%c)%c;   相加取余（相减也类式）
           (a*b)%c=((a%c)*(b%c))%c;    相乘取余
这个可以扩展到多个数相乘或相加。
明白了这些，这题就好办了。

参考代码：（四位为什么WA！）三位却AC了。

#include<stdio.h>
#include<string.h>
#define L 1000010
char a[105];
int kt[10000],k,prime[L];
int save(int h)
{  
	int sum=0; 
	for(int i=k-1;i>=0;i--)    
	{
	//sum=(sum*10000+kt[i])%h;	
         sum=(sum*1000+kt[i])%h;//递归取余。 
	}
	return sum;
}

int main()    
{  
	int flag,b,i,m=1;
	prime[0]=2;
	for(i=3;i<L;i+=2)    //素数 筛选 
	{ 
		 flag=1;
		for(int j=0;prime[j]*prime[j]<=i;j++)
			if(i%prime[j]==0)
			{ 
			   flag=0;
			   break;
			 }
		if(flag)
		 prime[m++]=i;
	 }					
	while(scanf("%s%d",a,&b),b)
	{  
		memset(kt,0,sizeof(kt));
		k=strlen(a);
		flag=1;
		for(int j=0;j<k;j++)
		{
			int r=(k+2-j)/3-1;   //不足三位的，暂时补足，减1代表了它是否超过三位。 
            //int r=(k+3-j)/4-1;
			kt[r]=kt[r]*10+(a[j]-'0');  
		}
		k=(k+2)/3;
		//k=(k+3)/4;
		for(i=0;prime[i]<b;i++)
		{
		   if(!save(prime[i]))
		    {		
         		flag=0;
				break;
			}
		}
		if(flag)
		  printf("GOOD\n");
		else
		  printf("BAD %d\n",prime[i]);
	}
	return 0;
}

筛选方法一：    其中 MAX=1000100    ,p[MAX];

for (int i = 4; i <= MAXN; i += 2) {
		p[i] = 1;
	}
	int LIM = (int)sqrt(1.0*MAXN);
	for (int i = 3; i <= LIM; i += 2) {
		if (p[i]) continue;
		int k = 2 * i;
		for (int j = i*i; j <= MAXN; j += k) {
			p[j] = 1;	
		}
	}
	for (int i = 2; i <= MAXN; ++i) {
		if (!p[i]) rec[++idx] = i;
	}
}

筛选方法二：线性筛选

void getprime() {
	idx = -1;
	for (int i = 2; i <= MAXN; ++i) {
		if (!p[i])
                        {
			rec[++idx] = i;
		        }
		for (int j = 0; rec[j]*i <= MAXN; ++j) {
			p[rec[j]*i] = 1;
			if (i % rec[j] == 0) {
				break;
			}
		}
	}