Prime Factorization Calculator — Find Prime Factors Instantly
Enter any positive integer up to 1,000,000,000 to instantly calculate its prime factorization — breaking the number down into its prime factor components with exponents. The tool shows the complete factorization, a table of each prime factor and its power, and identifies whether the number is itself prime.
Prime Factorization
360 = 2³ × 3² × 5
| Prime Factor | Exponent (pⁿ) | Value |
|---|---|---|
| 2 | 2³ | 8 |
| 3 | 3² | 9 |
| 5 | 1 | 5 |
Exponential notation: 2^3 × 3^2 × 5
How it works
What is prime factorization?
Prime factorization is the process of expressing a composite number as a product of prime numbers. A prime number is a whole number greater than 1 that has no divisors other than 1 and itself (2, 3, 5, 7, 11, 13, ...). The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written as a unique product of primes — the factorization is always the same regardless of how you find it.
For example: 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. The exponents show how many times each prime appears as a factor. The number 1 is not prime (it has only one divisor), and prime numbers themselves have exactly one factor — themselves. This tool uses trial division: it tries dividing by each integer starting from 2 up to the square root of the input, which is efficient for numbers up to one billion.
Applications of prime factorization
Prime factorization is the foundation of several important mathematical operations. Finding the Greatest Common Divisor (GCD) of two numbers: take the product of the shared prime factors at their lowest exponents. Finding the Least Common Multiple (LCM): take the product of all prime factors at their highest exponents. For example, GCD(360, 450) = 2¹ × 3² × 5¹ = 90, because 360 = 2³ × 3² × 5 and 450 = 2 × 3² × 5², and you take the minimum exponent for each prime.
In cryptography, the difficulty of factorizing large numbers into primes is the security basis for RSA encryption. The RSA algorithm uses two very large primes multiplied together — the product (the public key modulus) is easy to compute, but factoring it back into the original primes is computationally infeasible for large enough numbers. This one-way mathematical trap door is why RSA with 2048-bit keys remains secure despite decades of cryptanalysis.
The Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic (also called the Unique Factorization Theorem) states two things: (1) every integer greater than 1 can be expressed as a product of primes, and (2) this expression is unique up to the order of the factors. This theorem was known to Euclid and was proved rigorously in the 19th century. It means there is exactly one prime factorization for each number — no ambiguity.
The theorem does not hold in all number systems. In the Gaussian integers (complex numbers a + bi where a and b are integers), for example, some numbers can be factored in more than one way. The unique factorization property is what makes ordinary integers particularly well-behaved for arithmetic and is the reason prime factorization is so fundamental in number theory, algebra, and cryptography.
Frequently asked questions
›What is a prime factor?
A prime factor is a factor of a number that is also a prime number (divisible only by 1 and itself). For example, the prime factors of 12 are 2 and 3, because 12 = 2 × 2 × 3 = 2² × 3. The number 4 is a factor of 12 but not a prime factor, because 4 = 2 × 2 is not prime.
›How do you find the prime factorization of a number?
The simplest method is trial division: divide the number by the smallest prime (2) as many times as possible, then move to the next prime (3), and continue until the remaining number is 1. For 360: 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. So 360 = 2³ × 3² × 5. You only need to check primes up to the square root of the number — if none divide it, the number itself is prime.
›What is the prime factorization of 1?
The number 1 has no prime factors. By convention, 1 is not prime — it is the empty product (a product of zero primes). The Fundamental Theorem of Arithmetic applies to integers greater than 1. The number 0 is also excluded since any number times 0 equals 0, making factorization meaningless.
›What is the difference between prime factorization and factoring?
Factoring (or factorization) in general means expressing a number as a product of any integers (e.g., 12 = 4 × 3 or 12 = 6 × 2 or 12 = 12 × 1). Prime factorization specifically requires all factors to be prime. The prime factorization is unique; general factorizations are not. In algebra, factoring polynomials (like x² − 4 = (x−2)(x+2)) is a related but different concept.
›How is prime factorization used to find GCD and LCM?
GCD (Greatest Common Divisor): multiply together the shared prime factors at their minimum exponent. LCM (Least Common Multiple): multiply all prime factors at their maximum exponent. Example: 360 = 2³ × 3² × 5 and 450 = 2 × 3² × 5². GCD = 2¹ × 3² × 5¹ = 2 × 9 × 5 = 90. LCM = 2³ × 3² × 5² = 8 × 9 × 25 = 1800. Verify: GCD × LCM = 90 × 1800 = 162,000 = 360 × 450.
›What is the largest number this calculator can factorize?
This tool handles integers up to 1,000,000,000 (one billion). Trial division up to the square root of 1 billion is about 31,623 steps — fast enough for instant browser computation. For larger numbers, more sophisticated algorithms like Pollard's rho, quadratic sieve, or general number field sieve are used. Factoring a 300-digit semiprime (product of two large primes) would take longer than the age of the universe with current technology — which is why RSA encryption is secure.
›Is every even number divisible by 2?
Yes. By definition, an even number is any integer divisible by 2, so 2 is always a prime factor of every even number (except 2 itself, which is prime). In the prime factorization, even numbers always include 2 with exponent ≥ 1. For example: 100 = 2² × 5², 256 = 2⁸, 630 = 2 × 3² × 5 × 7.
›Can negative numbers be prime factorized?
Strictly in number theory, prime factorization applies to positive integers. Negative integers can be expressed using a factor of −1: for example, −12 = −1 × 2² × 3. However, −1 is not a prime number by the standard definition (a prime must be greater than 1). In abstract algebra, the concept generalizes to prime elements in rings, where both −1 and 1 are considered 'units,' not primes. This tool accepts only positive integers ≥ 2.
Related tools
Last updated: