[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)
24.181239102443353
Only 25 divmods; then, of course, 25 multiplications to calculate the
actual zero count.
More information about the Tutor
mailing list