On Sat, 6 Sep 2008, John Fouhy wrote: > 2008/9/5 Terry Carroll <[EMAIL PROTECTED]>: > > 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. _______________________________________________ Tutor maillist - [email protected] http://mail.python.org/mailman/listinfo/tutor
