2011上交:整除问题

题目描述：

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

输入：

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

输出：

一个整数.

样例输入：

6 10

样例输出：

1

#include <cstdio>
using namespace std;
int main()
{
    int n,a;
    while(scanf("%d%d",&n,&a)!=EOF)
    {
        int cnt=0;
        int sum=1;
        for(int i=n;i>=1;i--)
        {
            sum*=i;
            while(sum%a==0)
            {
                cnt++;
                sum/=a;
            }
            sum%=a;
        }
        printf("%d
",cnt);
    }
    return 0;
}