Input interpretation
prime factorization
Alternate names
integer factorization | prime decomposition
Basic definition
The factorization of a number into its constituent primes. Also called prime decomposition.
Detailed definition
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 became the first to establish that prime factorization lies in the complexity class NP.
Related topics
distinct prime factorization | distinct prime factors | economical number | equidigital number | factorization | ordered factorization | primary | prime factor | prime factorization algorithms | prime number | roundness | round number | wasteful number
Related Wolfram Language symbol
Educational grade level
elementary school level (California grade 5 standard)