组合数

来自闫老师的每日一题：

题目链接：https://leetcode-cn.com/problems/factorial-zeros-lcci/

n!表示n的阶乘，并且有n! = 1 * 2 * ····*n;求n!中有多少个质因子p

来自算法笔记的一种做法

// 计算n!中有多少个质因子p
int cal(int n,int p)
{
    int ans = 0;
    while(n)
    {
        ans += n / p;
        n = n / p;
    }
    
    return ans;
}

 

利用这个算法可以快速计算出n!的末尾有多少个零：需要计算因子10的个数，而10的个数又等于质因子5的个数（原文中写到为什么不是求质因子2的个数，我从网上找到了一种理解：10！= 1*2*3*4*5*6*7*8*9*10 很容易知道有有8个2相乘，和2个5相乘那么也就是末尾有2个0，而10！=3628800，也是2个0，而且因为是阶层，所以2的个数绝对是大于等于5的个数的，所以也可以只统计多少存在个5相乘），所以通过求n的阶乘中质因子5的个数就能求出0的个数