Optimising n! - revisited
For the background, see this post.
Late one night I thought that you might be able to simplify n-factorial thus:
`\prod_(i=1)^(\phi(n))p(i)^(\lfloorn/(p(i))\rfloor)`
Where:
- n is the number whose factorial we wish to calculate;
- p(i) is the ith prime number;
- Φ(n) is the number of primes less than or equal to n
Now, without using a lookup table, p() and Φ() are hard to calculate, but at least you'd avoid a lot of the problems that come from using the stupendously big numbers that come as intermediate results in calculating factorials.
Unfortunately, that formula is wrong anyway. It's a restatement of this:
100! = 250 * 333 * 520 * 714 * 119 * ...
which came from noticing that 100! is the product of 50 numbers which have 2 as a prime factor, 33 numbers which have 3 as a prime factor, 20 numbers that have 5 as a prime factor, and so on. Unfortunately, it doesn't take account of numbers like 4 and 18 which have a repeated prime factor - 4, for example, is 2 * 2 and 18 is 2 * 3 * 3. Bother.