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.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…