The factorization of a number into its constituent primes, also called prime decomposition. Given a
positive integer , the prime factorization is written
where the s
are the
prime factors, each of order
. Each factor
is called a primary.
Prime factorization can be performed in the Wolfram
Language using the command FactorInteger[n],
which returns a list of
pairs.
Through his invention of the Pratt certificate, Pratt (1975) became the first to establish that prime factorization lies in the complexity class NP.
The following Wolfram Language code can be used to give a nicely typeset form of a number :
FactorForm[n_?NumberQ, fac_:Automatic] :=
Times @@ (HoldForm[Power[##]]& @@@
FactorInteger[n, fac])
The first few prime factorizations (the number 1, by definition, has a prime factorization of "1") are given in the following table.
| prime factorization | prime factorization | ||
| 1 | 1 | 11 | 11 |
| 2 | 2 | 12 | |
| 3 | 3 | 13 | 13 |
| 4 | 14 | ||
| 5 | 5 | 15 | |
| 6 | 16 | ||
| 7 | 7 | 17 | 17 |
| 8 | 18 | ||
| 9 | 19 | 19 | |
| 10 | 20 |
The number of digits in the prime factorization of , 2, ..., are 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 2, 3, (OEIS A050252).
In general, prime factorization is a difficult problem, and many sophisticated prime factorization algorithms have been devised for special types of numbers.
Integers can also be factored over the Gaussian primes. For example, the following table gives the Gaussian integer factorizations for the first few positive integers.
| factorization | |
| 1 | 1 |
| 2 | |
| 3 | 3 |
| 4 | |
| 5 | |
| 6 | |
| 7 | 7 |
| 8 | |
| 9 | |
| 10 |
Interestingly, prime numbers equal to 1 (mod 4) can always by factored into Gaussian primes
in the form
where the real and imaginary parts are inverted in the two parts, while prime numbers equal to 3 (mod 4) cannot be factored into Gaussian primes. This is directly related to Fermat's 4n+1 theorem.