阶乘因式分解（一）（C/C++语言代码）

原题链接：题目56 - ACM在线评测系统

时间限制：3000 ms  |  内存限制：65535 KB

难度：2

描述

给定两个数m,n,其中m是一个素数。

将n（0<=n<=10000）的阶乘分解质因数，求其中有多少个m。

输入

第一行是一个整数s（0<s<=100)，表示测试数据的组数
随后的s行, 每行有两个整数n，m。

输出

输出m的个数。

样例输入

2
100 5
16 2

样例输出

24
15

解题思路：

每当输入一组n、m后，从大到小，从n到m，取得n!中的因数d，若d能被m整除，继续寻找d/m的商是否能被m整除，并为质因数计数。

注意事项：

用循环或递归都可以实现以上思路，建议少用或不用递归，如果一定要递归，是否可以改编成栈，调用函数前的断点状态逐步入栈，有返回值后逐步出栈？

参考代码：

int main(){
	int a,c,d,n,m;
	scanf("%d",&a);
	while(a--){
		scanf("%d%d",&n,&m);
		c=0;
		while(n>=m){//从大到小
			d=n;//取得n!中的一个因数d
			while(!(d%m)){//若d能被m整除
				d/=m;//继续寻找d/m的商
				c++;//为质因数计数
			}
			n--;
		}
		printf("%d\n",c);
	}
	return 0;
}

优秀代码

#include<iostream>
using namespace std;
int get(int n,int num)
{
	if(n==0) return 0;
	else return get(n/num,num)+n/num;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int a,b;
		cin>>a>>b;
		cout<<get(a,b)<<endl;
	}
	return 0;
}