Optimising n! - revisited
For the background, see this post.
Late one night I thought that you might be able to simplify n-factorial thus:
Take the product of p(i)int(n/p(i)) for i=1 to i=Φ(n). Damnit, I wish there was a good and easy way of writing mathemagics on t'interwebnet.
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.