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
 
這樣每個合數會被vis到的次數為該數的因子數，一個數的因子數比他的素因子數大很多，而n的素因子個數是logn的，效率很低。
 
一種比較快的方法：
primes[max_prime_num],num=0;
memset(vis,0,sizeof(vis));
for(int i=2;i這樣每個合數被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 
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=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=L) puts("GOOD");
		else printf("BAD %d\n",primes[i]);	
	}
	return 0;	
}