Category:Factorials with prime factorization

From LiteratePrograms
Jump to: navigation, search

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

\sum_{i=1}^{\infty} \, \lfloor n/p^i \rfloor.

Notice that this is actually a finite sum, since the floor is zero whenever pi > n. This implementation is based on the following references:

hijacker
hijacker
hijacker
hijacker

Pages in category "Factorials with prime factorization"

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