Prime Factorization Engine

Break any integer down into its core prime components. See the factor tree, expanded array, and exponential form instantly.

Input
-
Distinct Primes
-
Total Factors
-
Is Prime?
-
Expanded Array
Enter a number to begin...
Exponential Form
-
Factor Tree
Enter a number above to generate the factor tree.
Quick Divisibility Rules Cheat Sheet
2
Divisible by 2: the last digit is even (0, 2, 4, 6, or 8).
3
Divisible by 3: the sum of all digits is a multiple of 3. (e.g., 123: 1+2+3=6)
4
Divisible by 4: the last two digits form a number divisible by 4. (e.g., 312: 12 / 4 = 3)
5
Divisible by 5: the last digit is 0 or 5.
6
Divisible by 6: the number is divisible by both 2 and 3.
7
Divisible by 7: double the last digit, subtract it from the rest, and the result is divisible by 7. (e.g., 161: 16 - 2 = 14)
8
Divisible by 8: the last three digits form a number divisible by 8. (e.g., 1,024: 024 / 8 = 3)
9
Divisible by 9: the sum of all digits is a multiple of 9. (e.g., 729: 7+2+9=18)
10
Divisible by 10: the last digit is 0.
11
Divisible by 11: the alternating sum of digits is divisible by 11. (e.g., 1,331: 1-3+3-1=0)
Key Terms Explained
Prime Number
A natural number greater than 1 with exactly two divisors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13.
Composite Number
A natural number greater than 1 that has at least one positive divisor other than 1 and itself. Examples: 4, 6, 8, 9, 10.
Prime Factorization
The process of expressing a composite number as a product of its prime factors. Every integer greater than 1 has exactly one such representation.
Fundamental Theorem of Arithmetic
States that every integer greater than 1 is uniquely representable as a product of prime numbers (ignoring order). The guarantee that prime factorization is always unique.
Exponent
In the context of prime factorization, the exponent tells you how many times a particular prime factor appears. For example, 2 to the power 3 means the prime 2 appears three times.
Factor Tree
A visual diagram that repeatedly splits a composite number into two factors, branching downward until all leaf nodes are prime. A teaching tool used in mathematics education.
Prime Factor
A factor of a number that is itself a prime. Finding all prime factors of a number is the goal of prime factorization.
Divisibility
A number A is divisible by B if dividing A by B yields a whole number with no remainder. Divisibility rules are shortcuts to test this without performing full division.
Cryptography
The science of securing information. Modern public-key cryptography (like RSA) relies on the computational difficulty of factoring very large numbers into their primes.
Trial Division
The simplest factorization algorithm: test each integer from 2 up to the square root of the target. Efficient for numbers within the safe integer range used by this tool.

The Complete Guide to Prime Factorization

Prime factorization is one of the most fundamental operations in mathematics. Whether you are simplifying fractions, computing the least common multiple for algebra homework, or studying the number theory that underpins modern internet security, understanding how to break a number down to its prime core is an essential skill. This tool does the heavy lifting instantly, but understanding the process behind it makes the results far more meaningful.

How to Use This Tool

Type any positive integer into the large input field above. The engine updates in real time as you type, so there is no button to press. You will immediately see the expanded array (each prime factor listed individually), the exponential form (primes grouped with their exponents using superscript notation), an interactive factor tree, and four hero metrics summarizing the result. Numbers 0 and 1 are treated as special edge cases with their own explanatory text, and any value exceeding the browser's safe integer limit triggers a polite warning.

How the Algorithm Works

The engine uses an optimized trial division approach. It begins by checking divisibility by 2 (the only even prime) and extracts all factors of 2 first. It then steps through odd integers from 3 upward, testing each as a potential divisor. Crucially, it only tests up to the square root of the remaining value at each step. If a number n has no factor at or below its square root, then n itself must be prime. This reduces the worst-case number of checks from n to the square root of n, which is a massive performance gain for large inputs.

The Factor Tree Visual

The factor tree is generated by a recursive algorithm that splits a composite number into its smallest prime factor and the remaining quotient, then repeats the process on the quotient until all leaves are prime. Cyan-colored nodes are primes (leaves). Indigo-outlined nodes are composite (still being broken down). The tree grows downward, branching at each composite split, and terminates when every branch ends on a prime.

Real-World Applications

Beyond classroom math, prime factorization has concrete applications. Finding the GCD (greatest common divisor) or LCM (least common multiple) of two numbers is trivial once you have their prime factorizations: the GCD uses the minimum exponent of each shared prime, and the LCM uses the maximum. In cryptography, RSA encryption is built on the assumption that multiplying two large primes is easy, but factoring their product back into those primes is computationally hard with current hardware. The security of online banking, e-commerce, and private communications depends directly on this asymmetry.

Frequently Asked Questions

What is the Fundamental Theorem of Arithmetic?
The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number itself, or can be expressed as a unique product of prime numbers up to the order of the factors. This means the prime factorization of any number is one-of-a-kind: no two different integers share the exact same set of prime factors with the same exponents. It is the bedrock of number theory and guarantees that the output of this calculator is always the one correct answer.
Why is the number 1 not considered a prime number?
A prime number is defined as a natural number greater than 1 with exactly two distinct positive divisors: 1 and itself. The number 1 has only one positive divisor (itself), so it fails this definition. Excluding 1 from the primes also preserves the uniqueness guaranteed by the Fundamental Theorem. If 1 were prime, every number would have infinitely many factorizations (e.g., 6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3, and so on), making the theorem useless.
Why is prime factorization so important for computer encryption (RSA)?
RSA encryption relies on the mathematical asymmetry between multiplication and factorization. Multiplying two large prime numbers together takes a fraction of a second even on modest hardware. But reversing that process (finding the two original primes from their product) is computationally infeasible for numbers with hundreds of digits using all the computing power on Earth. This one-way difficulty is what makes RSA secure. Your private key is essentially the prime factorization of a massive public number. As long as factoring that number remains hard, the encryption holds.
How can you tell if a number is prime?
The most practical method for smaller numbers is trial division: test whether any integer from 2 up to the square root of the target divides it evenly. If none do, the number is prime. You only need to test up to the square root because if a number n has a factor larger than its square root, the paired factor must be smaller and would already have been found. For example, to test whether 97 is prime, check divisors up to 9 (the square root of 97 is about 9.8). None divide evenly, so 97 is prime. This tool displays "Yes" in the "Is Prime?" metric box for confirmed primes.
What is the difference between a prime factor and a regular factor?
A factor (or divisor) of a number n is any integer that divides n evenly with no remainder. The factors of 12 are 1, 2, 3, 4, 6, and 12. A prime factor is a factor that is also a prime number. The prime factors of 12 are only 2 and 3, because those are the only primes in the full factor list. Prime factorization goes further: it identifies the exact combination of prime factors, with their correct repetition counts (exponents), that multiply together to recreate the original number: in this case, 2 squared times 3.