pku2992 Divisors

http://poj.org/problem?id=2992
数学，质数，快速求n!中质数p的个数
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int valid[441] = {0};
 5 int ans[100], tot = 0;
 6 
 7 //O(N)筛质数表
 8 void get_prime(int n)
 9 {
10     int i, j;
11     for(i=2; i<=n; i++)
12     {
13         if(valid[i] == 0)
14         {
15             tot ++;
16             ans[tot] = i;
17         }
18         for(j=1; ((j<=tot) && (i*ans[j]<=n)); j++)
19         {
20             valid[i*ans[j]] = 1;
21             if(i%ans[j] == 0)
22             {
23                 break;
24             }
25         }
26     }
27 }
28 
29 //求n!中质数p个个数
30 int f(int n, int p)
31 {
32     return ( n<p? 0: n/p + f(n/p, p) );
33 }
34 
35 int main()
36 {
37     long long r;
38     int i, x, y;
39     get_prime(440);
40     while(~scanf("%d%d", &x, &y))
41     {
42         r = 1;
43         for(i=1; i<=tot && ans[i] <= x; i++) 
44         {
45             r *= (f(x, ans[i]) - f(y, ans[i]) - f(x-y, ans[i]) + 1);
46         }
47         printf("%lld\n", r);
48     }
49     return 0;
50 }