On 9/25/07, Terry Carroll <[EMAIL PROTECTED]> wrote: > > On Tue, 25 Sep 2007, Ian Witham wrote: > > > I am attempting to do this <https://www.spoj.pl/problems/FCTRL/> project > for > > the Sphere Online Judge. > > (Summary of the problem: for a given integer N, determine the number of > trailing zeroes in N! For example, for N=10, N! = 3628800, so the number > of trailing zeroes is 2.) > > > for d in testnums: > > maxer = int(d ** .2) + 1 > > g = sum(d / (5 ** x) for x in xrange(1, maxer)) > > sys.stdout.write('%d\n' % g) > > > > ############ > > > > Any ideas on how to speed this up? > > I think you're on the right track, but it can actually be much less > computationally intensive. > > The track I think you're on is that each trailing zero means that the > factorial, if factored out, had both a 2 and 5 among its factors (because > 2x5 is 10, and the only way of getting 10). Furthermore, because there > are so many 2s, it's really about counting the number of times 5 is > multiplied in. > > For example, in 10!, you have two occurances of 5: at 5 itself, and at 10 > (2x5). For 30!, you'd have fives at 5, 10, 15, 20, 25, and 30, which at > first glance is 6; but since the 25 is actually 5x5, it counts for two, > for a total of 7. And, sure enough 20! is > 265252859812191058636308480000000, with 7 trailing zeoes. > > So, an approach might be: > > 1. Integer-divide N by 5. That gives the number of times it's divisible > by 5. > 2. Integer-divide N by 5*5, i.e., 25; That gives the number of times it's > also divisible by 25. > 3. Integer-divide N by 5*5*5, i.e, 125. That gives the number of times > it's also divided by 125 > 4. through whatever: keep doing this. You can stop when the result of the > integer division is zero.
The problem with my program was the "through whatever". As I was using a list comprehension I wasn't sure how to make the calculations stop when the result of integer division == 0. My method was to work out the maximum exponent of 5 that I would fit within the test number. (This is the value I called "maxer") However... my math was off. int(d ** (1 / 5.0) != int(math.log(d, 5)) Once I fixed this, the program ran fast enough to be accepted. Thanks for the advice, Ian.
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
