poj 2635 The Embarrassed Cryptographer 筛素数+高精度除法

题意：

给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;	
}