c - 阶乘中的尾随零

Question

我正在尝试编写一个代码来计算特定数字(大数字)的阶乘中尾随零的数量。然而，对于小数字，我得到正确的结果，但对于大数字，偏差不断增加。我的逻辑有什么问题

#include <stdio.h>

int main(void) {
    int t;

    scanf("%d", &t);
    while (t > 0) {
        int factorten = 0, factorfive = 0, factortwo = 0, remainingfive = 0,
            remainingtwo = 0;
        unsigned int factors = 0;
        unsigned int n;
        scanf("%u", &n);
        for (unsigned int i = n; i > 0; i--) {
            if (i % 10 == 0) {
                factorten++;
                continue;
            } else if (i % 5 == 0) {
                factorfive++;
                continue;
            } else if (i % 2 == 0) {
                // int new = i;
                // while(new % 2 == 0)
                //{
                // new = new / 2;
                factortwo++;
                //}
                continue;
            }
        }

        factors = factors + factorten;
        printf("%u\n", factors);
        if (factorfive % 2 == 0 && factorfive != 0) {
            factors = factors + (factorfive / 2);
        } else {
            remainingfive = factorfive % 2;
            factors = factors + ((factorfive - remainingfive) / 2);
        }
        printf("%u\n", factors);
        if (factortwo % 5 == 0 && factortwo != 0) {
            factors = factors + (factortwo / 5);
        } else {
            remainingtwo = factortwo % 5;
            factors = factors + ((factortwo - remainingtwo) / 5);
        }
        printf("%u\n", factors);
        if ((remainingfive * remainingtwo % 10) == 0 &&
            (remainingfive * remainingtwo % 10) != 0) {
            factors++;
        }
        printf("%u\n", factors);
        t--;
    }
}

示例输入:

6
3
60
100
1024
23456
8735373

示例输出:

0
14
24
253
5861
2183837

我的输出

0
13
23
235
5394
2009134

Answer 1

编辑:忽略前两个，它们不是最佳的。第三种算法是最优的。

我认为这符合您想要做的，但更简单并且有效:

int tzif(int n)
{
    int f2 = 0, f5 = 0;
    for (;n > 1; n--)
    {
        int x = n;
        for (;x % 2 == 0; x /= 2)
            f2++;
        for (;x % 5 == 0; x /= 5)
            f5++;
    }
    return f2 > f5 ? f5 : f2;
}

它计算数字 N...2 的 2 因数和 5 因数。然后它返回两者中较小的一个(因为如果不添加 5 因子，添加 2 因子是没有用的，反之亦然)。你的代码太奇怪了，我无法分析。

我认为这也应该有效，因为阶乘将有足够的 2 因子来“覆盖”5 因子:

int tzif(int n)
{
    int f5 = 0;
    for (;n > 1; n--)
        for (x = n;x % 5 == 0; x /= 5)
            f5++;

    return f5;
}

这只计算 5 个因子并返回它。

我认为应该有效的另一种方法:

int tzif(int n)
{
    int f5 = 0;
    for (int d = 5; d <= n; d *= 5)
        f5 += n / d;

    return f5;
}

计算每五个数字(每个数字有一个 5 因子)，然后每第 25 个数字(每个数字有另一个 5 因子)，依此类推。