[Tutor] Need help with Factorial algorithm using Python

Terry Carroll carroll at tjc.com
Sat Sep 6 07:02:20 CEST 2008

On Fri, 5 Sep 2008, Terry Carroll wrote:

> On Sat, 6 Sep 2008, John Fouhy wrote:
> > You can count the number of fives in the prime decomposition of a
> > number by just dividing by 5 repeatedly until you don't get a whole
> > number.
> But that requires having the number first, doesn't it?  In other words, 
> don't you have to calculate N! in order to find out how many terminal 
> zeroes N! has?

Ah, never mind, I took a closer look at your code.  We're on a very 
similar tracks.

But the number of divisions you do scales up substantially for very large 
numbers.  By working with successive powers of 5 instead, you would only 
need to do log(N,5) divmods; for N=7*20:

>>> math.log(7**20,5)

Only 25 divmods; then, of course, 25 multiplications to calculate the
actual zero count.

More information about the Tutor mailing list