Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

c - Trailing zeroes in a Factorial

I am trying to write a code for calculating the number of trailing zeroes in a factorial of a specific number (large numbers). However, for small numbers, i get the correct result, but for large the deviations keeps increasing. What's wrong with my logic

#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
", factors);
        if (factorfive % 2 == 0 && factorfive != 0) {
            factors = factors + (factorfive / 2);
        } else {
            remainingfive = factorfive % 2;
            factors = factors + ((factorfive - remainingfive) / 2);
        }
        printf("%u
", factors);
        if (factortwo % 5 == 0 && factortwo != 0) {
            factors = factors + (factortwo / 5);
        } else {
            remainingtwo = factortwo % 5;
            factors = factors + ((factortwo - remainingtwo) / 5);
        }
        printf("%u
", factors);
        if ((remainingfive * remainingtwo % 10) == 0 &&
            (remainingfive * remainingtwo % 10) != 0) {
            factors++;
        }
        printf("%u
", factors);
        t--;
    }
}

Sample Input:

6
3
60
100
1024
23456
8735373

Sample Output:

0
14
24
253
5861
2183837

My OUTPUT

0
13
23
235
5394
2009134
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Edit: ignore the first two, they are suboptimal. The third algorithm is optimal.

I think this does what you're trying to do, but is a lot simpler and works:

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;
}

It counts 2-factors and 5-factors of numbers N...2. Then it returns the smaller of the two (because adding 2-factors is useless without adding 5-factors and vice-versa). Your code is too strange for me to analyze.

I think this should work too, because a factorial will have enough 2-factors to "cover" the 5-factors:

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

    return f5;
}

This only counts 5-factors and returns that.

Another method I think should work:

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

    return f5;
}

Count every fifth number (each has a 5-factor), then every 25-th number (each has another 5-factor), etc.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...