Back to the index. Or to the chambers
This article has 22 links. View as Cloud or List.
Loading ...
Planetmath Browser (2008—2009)
BSD licence | A django site
All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.
→ The original article on PlanetMath.org
Other Formats: LaTeX
De Polignacs Formula
Given 
, the prime factorization
of 
can be obtained by applying de Polignac's formula:
is the 
th prime
and 
is the prime counting function. For both the product
and the summation, the iterator's
end value can be set to infinity
and the formula is still correct. When
, dividing the former by the latter gives a value that floors
to zero, and then
. And when
then all 
give zero in the summation, and the multiplicand for the product is also 1. It is for the sake of a computer implementation that it is necessary
to stop the iterations
when they no longer give useful results.
A small disadvantage of de Polignac's formula is that it is necessary to know all the primes up to 
. If the implementation mistakenly iterates through a composite
value, the error might not be detected, while even
with a dumb implementation of trial division
(e.g., one that tries odd
composite values) the worst that can happen is that time is wasted by trying to divide
by a composite value whose prime factors
have already been divided out of the factorial.
Let's work out an example: factoring 10!. The primes less than 10 are 2, 3, 5 and 7. The base
2 logarithm
of 10 is approximately 3.32, meaning we only need to divide and floor up to 2's cube. Half 10 is 5, a quarter of 10 is 2.5 and an eighth of 10 is 1.25; adding up the integer parts
of these gives us 8, so the exponent
for 2 in the factorization of 10! is 8. The base 3 logarithm of 10 is approximately 2.0959. A third of 10 is about 3.3333 and a ninth of 10 is about 1.1111; the integer parts of these added up gives 4, so the exponent for 3 in the factorization is 4. For both bases
5 and 7, the logarithm of 10 is more than 1 but less than 2. 10 divided by 5 is 2, so that's our exponent for 5. 10 divided by 7 is about 1.42857, so 1 is our exponent for 7. Then we verify that indeed
