Primefactor

Primefactor refers to the representation of a positive integer as a product of prime numbers, possibly repeated. This expression is called the prime factorization. The Fundamental Theorem of Arithmetic states that every integer greater than 1 has a unique prime factorization, up to the order of the factors. Consequently, any number can be written as a product p1^e1 p2^e2 ... pk^ek where the pi are distinct primes and the ei are positive integers representing their multiplicities. The number 1 is regarded as having an empty factorization, and 0 is not factorizable in the same sense.

An example is 360 = 2^3 × 3^2 × 5, showing how primes appear with specific exponents that count their occurrences in the factorization. Prime factorization is useful for various purposes, such as simplifying fractions, solving certain types of Diophantine equations, and analyzing divisors and arithmetic properties of integers.

Computing prime factorization can be done by methods ranging from simple trial division by successive primes to more sophisticated algorithms for large integers, such as the Sieve of Eratosthenes (to generate primes) and factoring algorithms like Pollard’s rho or the elliptic curve method. In practice, factorization plays a central role in number theory and its applications, including cryptography, where the difficulty of factoring large composites underpins some encryption schemes.

See also: prime numbers, multiplicity, unique factorization, and the Fundamental Theorem of Arithmetic.