Prime Factorization

Prime factorization is 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 distinct prime factors and the s are positive integers. 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) established that the decision problem of primality testing lies in the complexity class NP.

The following Wolfram Language code can be used to give a nicely typeset factorization of an exact integer or rational number . With the default second argument Automatic, only factors that are easy to find are extracted, so the remaining cofactor may be a composite 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 decimal digits in the prime factorization counts the digits of each distinct prime factor and its exponent, with an exponent of 1 omitted and with 1 represented by a single digit. For , 2, ..., the counts 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 be factored into Gaussian primes in the form

where and are integers with and the real part and imaginary part are interchanged in the two factors. In contrast, prime numbers equal to 3 (mod 4) remain Gaussian primes. This is directly related to Fermat's 4n+1 theorem.