[Tutor] Need help with Factorial algorithm using Python
carroll at tjc.com
Sat Sep 6 06:50:39 CEST 2008
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
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.
More information about the Tutor