九度OJ 1104 整除问题

题目地址：http://ac.jobdu.com/problem.php?pid=1104

题目描述：

给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。

输入：

两个整数n(2<=n<=1000)，a(2<=a<=1000)

输出：

一个整数.

样例输入：

6 10

样例输出：

1

来源：

2011年上海交通大学计算机研究生机试真题

#include <stdio.h>
#include <string.h>
#include <math.h>
 
int IsPrime (int n){ 
    if (n <= 1) 
        return 0; 
    int sq = (int)sqrt((double)n); 
    while (sq >= 2){ 
        if (n % sq == 0) 
            break; 
        --sq; 
    } 
    return (sq >= 2) ? 0 : 1; 
} 
     
void Initialize(int Prime[], int n, int * primeSize){ 
    int index = 1; 
    int num = 3; 
     
    Prime[0] = 2; 
    while (num < n){ 
        if (IsPrime (num)){ 
            Prime[index] = num; 
            ++index; 
        } 
        num += 2; 
    }
    *primeSize = index;
}
 
 
 
int main(void){
    int n, a;
    int Prime[200];
    int primeSize;
    int cnt1[200], cnt2[200];
    int tmp;
    int i;
 
    Initialize(Prime, 1000, &primeSize);
    while (scanf ("%d%d", &n, &a) != EOF){
        memset (cnt1, 0, sizeof(cnt1));
        memset (cnt2, 0, sizeof(cnt2));
        for (i=0; i<primeSize; ++i){
            tmp = n;
            while (tmp){
                cnt1[i] += tmp / Prime[i];
                tmp /= Prime[i];
            }
        }
        int ans = 10000000;
        for (i=0; i<primeSize; ++i){
            while (a % Prime[i] == 0){
                ++cnt2[i];
                a /= Prime[i];
            }
            if (cnt2[i] == 0)
                continue;
            if (cnt1[i] / cnt2[i] < ans)
                ans = cnt1[i] / cnt2[i];
        }
        printf ("%d
", ans);
    }
 
    return 0;
}

参考资料：2013年王道论坛计算机考研机试指南