[Tutor] Need help with Factorial algorithm using Python

[Terry Carroll]

On Sat, 6 Sep 2008, John Fouhy wrote:

> 2008/9/5 Terry Carroll <carroll at tjc.com>:
> > So here's my routine to address the problem.  It consists of making a
> > multiplication table of coefficients that includes the factor such as 5,
> > 25, 125, etc., and their values (1, 6, 31, etc).  Then, starting with the
> > highest ones first, successievely determining how many times each factor
> > goes into the number of zeroes.  For example, to do the prior example
> > working backwards, what factorial will give you 71 zeroes?
> 
> I think there is a simpler solution :-)

Definitely, but most require calculating the factorial first, and for 
large factorials, that going to be a huge computational burden.

> 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?
 
The method I proposed determines the number of terminal zeroes in N! 
by examination of N, without calculating N!, which is a substantial 
computational savings when N is large; and in fact, makes the problem 
tractable for large values of N.

> Although I am curious to know how long it took your algorithm to find
> the answer for 7**20 ...

Under a second.  In a trial, I put "print time.asctime()" before and after 
the calculation, and it printed the same time in both print statements.  
How much under a second, I'm not sure.