题意：
给K(<10^100),L(<10^6),求K小于L的最小素因子并输出，如果没有则输出GOOD。
分析：
枚举小于L的素数用高精度除法判断是否是因子，关键是怎么高效筛素数，先给一种比较慢的筛法：primes[max_prime_num],num=0;memset(vis,0,sizeof(vis))for(int i=2;i<maxL;++i)if(vis[i]==0){prime[num++]=i;for(int j=2*i;j<maxL;j+=i)vis[i]=1;}
这样每个合数会被vis到的次数为该数的因子数，一个数的因子数比他的素因子数大很多，而n的素因子个数是logn的，，效率很低。
一种比较快的方法：primes[max_prime_num],num=0;memset(vis,0,sizeof(vis));for(int i=2;i<maxL;++i){if(!vis[i])primes[num++]=i;for(int j=0;j<num&&i*primes[j]<maxL;++j){vis[i*primes[j]]=1;if(!i%primes[j])break;}}这样每个合数被vis到的次数仅为1，如2^4*3^6只在i==2^3*3^6,primes[j]==2时被vis到，2*3*5只在i==3*5,prime[j]==2被vis到，效率高于第一种方法。
代码：
//poj 2635//sep9#include <iostream>using namespace std;int s[128],L,len;int tmp[128];char input[128];const int maxL=1000024;int vis[maxL+10];int primes[maxL+10],num;int divs(int q,int len){for(int i=0;i<len;++i)tmp[i]=s[len-1-i];tmp[len]=0;for(int i=0;i<len;++i){tmp[i+1]+=1000*(tmp[i]%q);tmp[i]/=q;}return tmp[len];}void ini(){memset(vis,0,sizeof(vis));num=0;for(int i=2;i<maxL;++i){if(!vis[i])primes[num++]=i;for(int j=0;j<num&&i*primes[j]<maxL;++j){vis[i*primes[j]]=1;if(!i%primes[j])break;}}}int main(){ini();while(scanf("%s%d",input,&L)==2){if(input[0]=='0'&&L==0)break;int t=0,cnt=0,sum=0,pow10[4]={1,10,100};len=strlen(input);for(int i=len-1;i>=0;–i){sum=pow10[cnt]*(input[i]-'0')+sum;if(cnt==2){s[t++]=sum;cnt=sum=0;}else++cnt;}if(sum!=0) s[t++]=sum;int i;for(i=0;i<num&&primes[i]<L;++i)if(divs(primes[i],t)==0)break;if(i==num||primes[i]>=L) puts("GOOD");else printf("BAD %d\n",primes[i]);}return 0;}
为你的快乐而快乐的是朋友，为你的难过而难过的才是你的知己。
