# [Tutor] Need help speeding up algorithm.

Ian Witham witham.ian at gmail.com
Wed Sep 26 01:06:31 CEST 2007

```On 9/26/07, Terry Carroll <carroll at tjc.com> wrote:
>
> On Tue, 25 Sep 2007, Ian Witham wrote:
>
> def numfaczeroes(n):
>     """
>     return the count of trailing zeroes from n!
>     e.g., 10! = 3628800; count of trailing zeros = 2
>     """
>     exponent = 1
>     fivecount = 0
>     while (n//(5**exponent)) > 0:
>         fivecount += n//(5**exponent)
>         exponent += 1
>     return fivecount
>

I've come up with a couple of improvements to your function

First I moved the (n//(5**exponent)) out of the while definition as it was
being evaluated twice for each iteration:

def numfaczeroes(n):
"""
return the count of trailing zeroes from n!
e.g., 10! = 3628800; count of trailing zeros = 2
"""
exponent = 1
fivecount = 0
count = (n//(5**exponent))

while count > 0:
fivecount += count
exponent += 1
count = (n//(5**exponent))
return fivecount

This shaved about 10% off the run time.

Then I got rid of the (n//(5**exponent)) altogether:

def numfaczeroes(n):
"""
return the count of trailing zeroes from n!
e.g., 10! = 3628800; count of trailing zeros = 2
"""

fivecount = 0
count = n//5

while count > 0:
fivecount += count
count /= 5
return fivecount

This shaved a further 40% off the run time!

In practice, the Sphere Judge still takes 3 seconds to execute. So perhaps
there is another bottleneck in my program -- maybe the input/output?

Interestingly, print runs faster than sys.stout.write, but input() is far

import sys

fivecount = 0
count = n/5

while count > 0:
fivecount += count
count /= 5

print fivecount
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20070926/de1c3016/attachment.htm
```