14.关于n的阶乘的问题重难点剖析

1.求n！中有多少个质因子p；

<mark>算法①： 复杂度（nlogn）</mark>
只适用于n很小的情况 [PASS]

int _sum(int n,int p)
{
	int ans=0;
	for(int i=2;i<=n;i++)
	{
		int temp=i;
		while(temp%p==0)  //如果有因子p +1 且除以p 直至没有因子p
		{
			ans++;
			temp/=p;
		}
	}
	return ans;
}

<mark>算法②：复杂度（logn）</mark>

int _sum(int n,int p)
{
	int ans=0;
	while(n)
	{
		ans+=n/p; //由数学公式推导 这里不再赘述
		n/=p;
	}
	return ans;
}

<mark>算法②：递归写法</mark> 个人记忆法：npnpp 谐音（你怕你婆婆）

int _sum(int n,int p)
{
	if(n<p) return 0;
	return n/p+_sum(n/p,p);
}

2.求阶乘末尾0的个数

<mark>思路：</mark>

int _sum(int n,int p)
{
	if(n<p) return 0;
	return n/p+_sum(n/p,p); //就是这里的p改成5 就可以了
}

源代码：

#include <bits/stdc++.h>
using namespace std;

int _sum(int n,int p)
{
	if(n<p) return 0;
	return n/p+_sum(n/p,p);  //个人记忆法：npnpp 谐音（你怕你婆婆）
}

int main()
{
	cout<<_sum(1024,5);  //如果求阶乘末尾0的个数 这里的p选择5即可 
	return 0;
}