TOPICS
Search

Prime Factorization


The factorization of a number into its constituent primes, also called prime decomposition. Given a positive integer n>=2, the prime factorization is written

 n=p_1^(alpha_1)p_2^(alpha_2)...p_k^(alpha_k),

where the p_is are the k prime factors, each of order alpha_i. Each factor p_i^(alpha_i) is called a primary. Prime factorization can be performed in the Wolfram Language using the command FactorInteger[n], which returns a list of (p_i,alpha_i) 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 n:

  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.

nprime factorizationnprime factorization
111111
22122^2·3
331313
42^2142·7
55153·5
62·3162^4
771717
82^3182·3^2
93^21919
102·5202^2·5

The number of digits in the prime factorization of n=1, 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.

nfactorization
11
2-i(i+1)^2
33
4-(i+1)^4
5-i(2i+1)(2+i)
6-3i(i+1)^2
77
8i(i+1)^6
93^2
10-(i+1)^2(2i+1)(i+2)

Interestingly, prime numbers p equal to 1 (mod 4) can always by factored into Gaussian primes in the form

 p=-i(R+Ii)(I+Ri),

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.


See also

Distinct Prime Factorization, Distinct Prime Factors, Economical Number, Equidigital Number, Factorization, Ordered Factorization, Primary, Prime Factorization Algorithms, Prime Factor, Prime Number, Round Number, Roundness, Wasteful Number Explore this topic in the MathWorld classroom

Related Wolfram sites

http://functions.wolfram.com/NumberTheoryFunctions/FactorInteger/

Explore with Wolfram|Alpha

References

Dickson, L. E. "Factor Tables, Lists of Primes." Ch. 13 in History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, pp. 347-356, 2005.Glaisher, J. Factor Tables for the Sixth Million: Containing the Least Factor of Every Number Not Divisible by 2, 3, or 5 between 5000000 and 6000000. London: Taylor and Francis, 1883.Lehmer, D. N. Factor Table for the First Ten Millions, Containing the Smallest Factor of Every Number Not Divisible by 2, 3, 5 or 7 Between the Limits 0 and 10017000. Washington, DC: Carnegie Institution of Washington, No. 105, 1909.Lehmer, D. N. List of Prime Numbers from 1 to 10006721. Washington, DC: Carnegie Institution, 1914.Peters, J.; Lodge, A.; Ternouth, E. J.; and Gifford, E. Factor Table: Giving the Complete Decomposition of All Numbers Less than 100000. London: British Association for the Advancement of Science, 1935.Pratt, V. "Every Prime Has a Succinct Certificate." SIAM J. Comput. 4, 214-220, 1975.

Referenced on Wolfram|Alpha

Prime Factorization

Cite this as:

Weisstein, Eric W. "Prime Factorization." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PrimeFactorization.html

Subject classifications