# SPOJ FCTRL

## Summary

This problem required us to determine the number of trailing zeroes for factorial n, where n is a integer between 1 and 1 billion. Obviously calculating n! itself and determining the number of trailing zeroes would result in a TLE, but if we research a bit we find a simple mathematical formula to determine Z(N):

${\displaystyle Z(N)=\sum _{k=1}^{\lfloor log_{5}N\rfloor }\lfloor {\frac {N}{5^{k}}}\rfloor }$

## Implementations

This is just a straightforward translation of the formula above:

int zeta(int n) {
int ret = 0;
for (int p = 5; p <= n; p*=5)
ret += n/p;
return ret;
}


## Input

6
3
60
100
1024
23456
8735373


## Output

0
14
24
253
5861
2183837


## References

1. Factorial - Wolfram Mathworld - [1]