SamCalculator

Prime Factorization Calculator

Find the prime factors of any positive integer, view the factor tree, and see the complete prime decomposition with step-by-step calculations.

Positive Integer

Try:

What Is Prime Factorization?

Prime factorization is the unique way of writing a positive integer greater than 1 as a product of prime numbers. The number 7,560, for example, breaks down as 2 × 2 × 2 × 3 × 3 × 3 × 5 × 7 — or in exponent form, 2³ × 3³ × 5 × 7. The Fundamental Theorem of Arithmetic guarantees that this decomposition is unique up to the order of the factors: every integer has exactly one prime fingerprint.

This calculator accepts any positive integer up to 10¹², returns the list of prime factors with multiplicity, builds a binary factor tree, shows the step-by-step division derivation, computes the number-theoretic functions τ(n) (divisor count) and σ(n) (divisor sum), and classifies the input as prime/composite, even/odd, perfect square, and perfect cube. It pairs well with the common factor calculator for GCF and LCM problems, the root calculator for radical simplification, and the scientific calculator for cross-checking arithmetic.

How the Calculator Works

Validate the input

The calculator accepts positive integers from 2 up to 10¹². Commas and spaces are stripped, so 1,234,567 and 1 234 567 both parse the same. Decimals, fractions, and negatives are rejected — prime factorization is defined only for whole numbers ≥ 2.

Trial-division factorisation

Starting at 2, the tool repeatedly divides the input by the smallest prime that fits and records each step. After 2, it tries odd primes 3, 5, 7, 11, … only up to √n, because any composite factor larger than √n already has a partner smaller than √n.

Build the factor tree

At every internal node the smallest prime divisor goes left and the cofactor goes right. Recursion continues on the cofactor until the leaves are all prime — exactly the prime factors of the input.

Compute number-theoretic statistics

The exponent vector feeds τ(n) = ∏(eᵢ + 1) for the divisor count and σ(n) = ∏ (pᵢ^(eᵢ+1) − 1) / (pᵢ − 1) for the divisor sum. Perfect-square and perfect-cube checks reduce to inspecting whether every exponent is divisible by 2 or 3.

6 Ways to Use This Calculator

1

Simplify radicals

Pull perfect-power factors out of square or cube roots. √7560 factors as √(2² × 2 × 3² × 3 × 5 × 7) = 6√210 — the factor tree shows the pairs to lift.

2

Find every divisor

τ(n) = ∏(eᵢ + 1) tells you how many positive divisors a number has without enumerating them. 7560 has 64 divisors because its exponent vector (3, 3, 1, 1) gives 4 × 4 × 2 × 2 = 64.

3

Compute GCF and LCM

Lined-up prime exponents give the GCF (min of each exponent) and the LCM (max of each exponent). The factor tree is the first step in both calculations.

4

Check perfect powers

A number is a perfect kᵗʰ power if and only if every exponent in its prime factorisation is divisible by k. The calculator flags perfect squares and perfect cubes automatically.

5

Reduce fractions to lowest terms

Cancel matched prime powers from numerator and denominator. The exponent table makes shared primes visible at a glance — pair this tool with the GCF calculator for one-step reductions.

6

Verify cryptography homework

RSA key generation, primitive roots, and Euler's φ all hinge on factorisation. Use this calculator to confirm small-prime worked examples before scaling to the proper Miller–Rabin / Pollard-rho regime.

Best Practices

Start with the smallest primes. Always test 2 first (handles every even input), then 3, 5, 7, 11, 13, and so on. Trial division has to test only primes up to √n because any larger prime factor would already have a smaller partner picked up earlier.

Use the factor tree to visualise — not to compute. The tree is a teaching aid: the same factorisation is reached by any choice of factor pairs at each split. This calculator picks the smallest prime at every step so the leaves come out in sorted order.

Read off τ(n) and σ(n) from the exponent vector. Once you have the prime factorisation, you don't have to enumerate divisors to count them or sum them. τ(n) = ∏(eᵢ + 1) and σ(n) = ∏ (pᵢ^(eᵢ+1) − 1) / (pᵢ − 1) work directly off the exponents.

Why Prime Factorization Matters

Foundation of arithmetic

The Fundamental Theorem of Arithmetic says every integer has one and only one prime factorisation. Without it, fractions would have multiple 'lowest terms' and number theory would have no anchor.

GCF, LCM, and modular math

Almost every classical number-theory identity is easier to read off the prime factorisation. GCF takes minimums of exponents, LCM takes maximums, and Euler's φ(n) factors directly through the prime decomposition.

Cryptography and computer science

RSA security rests on the hardness of factoring a product of two large primes. The same factorisation routines underpin primality testing, discrete-log work, and lattice-based cryptography.

Education and reasoning

Factor trees are the standard pedagogical tool for introducing prime decomposition in middle school. They make abstract divisibility concrete and form the bridge to harder ideas like the unique-factorisation theorem.

Tricky Cases

Prime inputs

A prime number — like 97, 211, or 7919 — factors as just itself. The calculator returns a single-leaf tree and flags the input as prime; there is nothing else to decompose.

Powers of one prime

Numbers like 1024 = 2¹⁰ or 6561 = 3⁸ produce a long ladder of identical splits. The exponent form is more compact than the expanded product and clearly communicates the structure.

Large prime co-factors

Inputs like 9991 = 97 × 103 or 9999 = 3² × 11 × 101 contain a large prime that trial division finds only after testing up to √n. The factor tree shows the small primes first; the last remaining quotient is the large prime.

1 is excluded

The number 1 has no prime factorisation under modern conventions — its 'factorisation' is the empty product. The calculator rejects 0, 1, and negatives because none of them have a non-trivial prime decomposition.

Core Formulas

Fundamental theorem

n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ

Every integer > 1 has a unique factorisation into prime powers (up to the order of the primes).

Divisor count τ(n)

τ(n) = ∏ (eᵢ + 1)

Number of positive divisors of n — count comes straight from the exponent vector. 7560 = 2³·3³·5·7 → τ = 4·4·2·2 = 64.

Divisor sum σ(n)

σ(n) = ∏ (pᵢ^(eᵢ+1) − 1)/(pᵢ − 1)

Sum of all positive divisors. For 7560 the sum is 19,344 — used in perfect-number and abundance arguments.

Perfect-power test

n is a k-th power ⇔ ∀i, k | eᵢ

Perfect squares need every exponent even; perfect cubes need every exponent divisible by 3; perfect kᵗʰ powers need every exponent divisible by k.

GCF via primes

gcd = ∏ pᵢ^min(eᵢ, fᵢ)

The greatest common factor of two numbers is the product of each shared prime raised to the minimum of its two exponents.

LCM via primes

lcm = ∏ pᵢ^max(eᵢ, fᵢ)

The least common multiple is the product of every prime that appears in either number, raised to the maximum exponent.

Common Mistakes

Treating 1 as prime

1 isn't prime — it has only one positive divisor, not two. Excluding 1 from the primes is what makes prime factorisation unique; otherwise 6 = 2·3 = 1·2·3 = 1·1·2·3 and the decomposition would have infinitely many forms.

Stopping factorisation too early

It's easy to write 60 = 4 × 15 and call it a factorisation — but 4 = 2² and 15 = 3 × 5 still need to be broken down. The tree isn't finished until every leaf is prime.

Confusing prime factor count with divisor count

7560 has 8 prime factors counted with multiplicity (three 2s, three 3s, one 5, one 7) but 64 divisors. The exponent vector translates one to the other via τ(n) = ∏(eᵢ + 1).

Trying every number, not just primes

Trial division only needs to test primes — every composite divisor would be caught by its prime factors first. Testing 4, 6, 8, 9 wastes time after you've already extracted all the 2s and 3s.

Built for students learning prime factorisation, teachers preparing factor-tree examples, math tutors checking homework, cryptography hobbyists verifying small-prime exercises, and engineers who need a quick handle on divisor structure. Every result returns the prime factors with multiplicity, exponent form, factor tree, step-by-step division, divisor count and sum, classification flags, and a multiplication verification — so you can confirm the math at every step.

Prime Factorization Calculator FAQs

Prime factorization is the unique way of writing a positive integer greater than 1 as a product of prime numbers. For example, 7560 = 2 × 2 × 2 × 3 × 3 × 3 × 5 × 7, or in exponent form 7560 = 2³ × 3³ × 5 × 7. The Fundamental Theorem of Arithmetic guarantees that this decomposition is unique up to the order of the factors — every integer ≥ 2 has exactly one prime factorisation.

Start by writing the input at the top. Pick any pair of factors whose product equals it (this calculator always picks the smallest prime and the remaining cofactor) and draw a branch to each. Repeat the same step on every composite child, and stop when every leaf is a prime. The collection of leaves — read left to right — is the prime factorization. Different factor choices give visually different trees but always the same set of leaves.

Prime factors are the prime numbers that multiply together to give the original integer. Counted with multiplicity, 7560 has eight prime factors (three 2s, three 3s, one 5, one 7); counted as distinct values, it has four (2, 3, 5, 7). 'Prime' here means a number whose only positive divisors are 1 and itself — 2, 3, 5, 7, 11, 13, 17, …

A prime number's factorization is just itself — 97 = 97, 211 = 211. The calculator returns a single-leaf factor tree and flags the input as prime. By convention 1 is not prime and has no prime factorization (its 'factorization' is the empty product, which equals 1).

Exponent notation collapses repeated prime factors into prime^count form. Instead of writing 2 × 2 × 2 × 3 × 3 × 3 × 5 × 7, you write 2³ × 3³ × 5 × 7. The format is shorter, makes it easy to spot perfect-power inputs (every exponent is divisible by 2 → perfect square, by 3 → perfect cube), and lets you compute τ(n) and σ(n) directly from the exponent vector without enumerating divisors.

Write the prime factorisation of every number. For each prime that appears in all of them, take the smallest exponent across the lists. Multiply those prime powers together to get the GCF. Example: 7560 = 2³ × 3³ × 5 × 7 and 1260 = 2² × 3² × 5 × 7, so GCF = 2² × 3² × 5 × 7 = 1260. The common-factor calculator wraps this up automatically for any number of inputs.

Take the union of all primes that appear in any input, raised to the largest exponent each prime has across the lists. For 12 = 2² × 3 and 18 = 2 × 3², the LCM is 2² × 3² = 36. Equivalently, LCM(a, b) = (a × b) / GCF(a, b) — once you have the prime factorisations, both routes give the same answer.

It's the biggest prime in the factorization list. For 7560 the prime factors are 2, 3, 5, 7 — so the largest prime factor is 7. For 9991 = 97 × 103 the largest is 103. The calculator displays this directly under the hero card so you can use it without scanning the list yourself.

The divisor count is τ(n) = ∏(eᵢ + 1) over the exponents in the prime factorisation — every divisor is a choice of 0..eᵢ copies of each prime, giving (e₁ + 1)(e₂ + 1)… combinations. The divisor sum is σ(n) = ∏ (pᵢ^(eᵢ+1) − 1) / (pᵢ − 1), the product of geometric series for each prime power. For 7560 = 2³·3³·5·7 these give 4·4·2·2 = 64 divisors summing to 19,344.

A positive integer is a perfect square if and only if every exponent in its prime factorisation is even. 144 = 2⁴ × 3² has exponents (4, 2) — both even — so 144 = 12². 7560 = 2³ × 3³ × 5 × 7 has exponents (3, 3, 1, 1) — none even — so it's not a perfect square. The same logic gives perfect kᵗʰ powers: every exponent must be divisible by k.

Related Calculators

Pair the prime factorization calculator with other math tools for common factors, radicals, scientific notation, and step-by-step number-theory work.