# Category:Factorials with prime factorization

The *n*th 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(*n*^{2} 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 *p*^{i} > *n*. This implementation is based on the following references:

- Peter Luschny.
*Fast Factorial Functions* - Peter Borwein. "On the Complexity of Calculating Factorials".
*Journal of Algorithms*6, 376-380 (1985) - Xavier Gourdon & Pascal Sebah.
*Binary splitting method*

## Pages in category "Factorials with prime factorization"

The following 2 pages are in this category, out of 2 total.