c语言大数阶乘和计算阶乘末尾的0的个数

一、大数阶乘的数据保存

大数进行阶乘，将数据保存在数组中。这样遍历数组，就可以打印出阶乘的结果。

核心计算就是：将阶乘的乘法转化为加法和进位

比如：计算6！= 2*3*4*5*6 ?设为i

初始result[1]=1,result.length=1,carry默认是0

i = 2 -------->result[1]=(i*result[1])%10=2,carry=0,没产生进位，数组长度不增加,result[1]=2

i = 3 -------->result[1]=(i*result[1])%10=6,result[1]=2

i = 4 -------->result[1]=(i*result[1])%10=24%10=4,carray=24/10=2,carry不为0，要产生进位，length++，此时result[1]=4,result[2]=0默认

result[2]=(i*result[2])%10=4*0+2=2,此时，result[1]=4,result[2]=2

i = 5 -------->result[1]=(i*result[1])%10=4*5%10=0,carray=20/10=2,carry不为0，要产生进位，length++，此时result[1]=0,result[2]=2

result[2]=(i*result[2])%10=(5*2+2)%10=2,carry=1,此时，result[1]=0,result[2]=2,继续产生进位

result[3]=(i*result[3]%10)=5*0+1=1,此时result[1]=0,result[2]=2，result[3]=1

那么倒序打印result数组，就是6！的值

代码

void BigFactorial(int targetNum)
{
    static int a[50000]= {0,1}; //第一位不用
    int carry = 0;//进位
    int tmp = 0;//临时变量
    int lenth=1;//已经保存的数组的长度

    for(int i=2; i<=targetNum; i++) //外循环负责计算阶乘
    {
        carry=0;
        for (int j=1; j<=lenth; j++) //内循环负责把阶乘的值保存到数组中
        {
            //乘法转化为加法和进位
            tmp=a[j]*i+carry;
            a[j]=tmp%10;
            carry=tmp/10;
            //如果有进位，则向前扩展一位
            //内循环再计算一次
            if (j==lenth&&carry!=0)
                lenth++;
            //如果没有产生进位，继续进行阶乘
        }
    }
    for(int k=lenth; k>=1; k--)
        printf("%d",a[k]);
}
int main()
{
    BigFactorial(1000);
    return 0;
}

1、首先考虑0的来源，来源与10

2、10可以分解为2*5，即只需要计算有多少对2*5,但2的倍数比5的倍数多，所以只需要计算5的倍数

int factorialof5(int i)
{
    int count=0;
    while(i % 5==0)
    {
        count++;
        i /= 5;
    }
    return count;
}

int countOf0(int number)
{
    int count=0;
    for(int i = 2; i<=number; i++)
        count += factorialof5(i);
    return count;
}

//或者直接数5的因数
//从1到number之间，有几个5的倍数

    long long trailingZeros(long long n) {
        if(n<=0)
            return -1;
        long long count = 0;
        for(int i = 5;n/i>0;i*=5)
            count += n/i;
        return count;
    }