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

     


     


     
?

     
?

     
?