求质因子个数

求n!中质因子的个数

1.暴力枚举计数法：

#include <iostream>
using namespace std;
int combine(int n,int p){int count=0;for(int i=2;i<=n;i++){//i作为循环变量int divide=i;//最好不同变量发挥一个功能，另设divide作为被除数除while(divide%p==0){//能被整除，说明有因子为p的质因子count++;//记录个数divide/=p;}}return count;//返回因子个数
}
int main(){int n,m;cin>>n>>m;cout<<combine(n,m)<<endl;return 0;
}

2.以因子y为比值，循环遍历：

#include <iostream>
using namespace std;
int combine(int x,int y){int count=0;while(x){//直至考虑完x中的数为止count+=x/y;//eg:4中因子2的个数-4/2，求x中因子y的个数x/=y;//求下一个含因子y的x}return count;
}
int main(){int n,m;cin>>n>>m;cout<<combine(n,m)<<endl;return 0;
}

3.递归调用：

#include <iostream>
using namespace std;
int combine(int x,int y){if(x<y) return 0;return x/y+combine(x/y,y);//不断递归累加
}
int main(){int n,m;cin>>n>>m;cout<<combine(n,m)<<endl;return 0;
}