The nth factorial, n!, can be computed straightforwardly by multiplying together the range of integers 1, 2, ... n from the bottom up. However, if n is large, this becomes inefficient. The k:th subproduct has roughly k log k digits, so multiplying by k+1 (assumed to fit in a single machine word) takes k log k time. This leads to a total time of O(n2 log n) for calculating n!.
Many algorithms exist for splitting a product of many factors into smaller pieces to balance the size of each subproduct. However, there is a trick to factorials: we can find the prime factorization of n! quickly, much more quickly than we can compute n! itself. And we can do this without stepping through the list 1, 2, ..., n and factorizing each of these numbers. The crucial observation is that n! must necessarily contain each prime number up to n, and that the power of the prime p in n! is given by
Notice that this is actually a finite sum, since the floor is zero whenever pi > n. This implementation is based on the following references:
Pages in category "Factorials with prime factorization"
The following 2 pages are in this category, out of 2 total.