描述
给定两个数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！ = 1*2*3*4*...*(n-2)*(n-1)*(n)依此判断每个因数中分别有多少个质因数m，相加便是结果。
#include<cstdio>
int main(){int i,j,k,m,n,s;scanf("%d",&s);while(s--){scanf("%d%d",&n,&m);int j=0;for(int i=m ;i<=n ;i++){//循环遍历因数 for(k=i ;!(k%m) ;j++){//计算因数中的质因数个数 k /= m;}}printf("%d\n",j);}return 0;
}