hdu 2303

地址：http://acm.hdu.edu.cn/showproblem.php?pid=2303

题意：输入2个数字k和l，第一个是大数（10^100），第二个数是一个上限（10^6）。问k是否有小于l的质因数，如果有，最小的是多少。

mark：时限卡的比较严，先把100w以内的素数打表，然后挨个检测素数，每次用大数对这个素数取模。若模为0则为素因子。

代码：

 1 # include <stdio.h>
 2 
 3 
 4 int cnt ;
 5 char k[110] ;
 6 int prime[1000010], isprime[1000010] ;
 7 
 8 
 9 void init()
10 {
11     int i, j ;
12     cnt = 0 ;
13     for (i = 0 ; i <= 1000000 ; i++) isprime[i] = 1 ;
14     for (i = 2 ; i <= 1000000 ; i++)
15     {
16         if (isprime[i]) prime[cnt++] = i ;
17         for (j = i*i ; i <= 1000 && j <= 1000000 ; j+=i)
18             isprime[j] = 0 ;
19     }
20 }
21 
22 
23 int mod(char s[], int m)
24 {
25     int i, ans = 0 ;
26     for (i = 0 ; s[i] ; i++)
27         ans = (ans*10+s[i]-'0') % m ;
28     return ans ;
29 }
30 
31 
32 int main ()
33 {
34     int i, l ;
35     init() ;
36     while (~scanf ("%s%d", k, &l))
37     {
38         if (l==0) break ;
39         for (i = 0 ; i < cnt && prime[i] < l ; i++)
40             if (mod(k, prime[i]) == 0) break ;
41         if (i == cnt || prime[i] >= l)
42             puts ("GOOD") ;
43         else printf ("BAD %d
", prime[i]) ;
44     }
45     return 0 ;
46 }