Prime Factorization Calculator

About Prime Factorization

Prime factorization is the process of breaking down a positive integer into a product of prime numbers. Every integer greater than 1 can be written as a unique product of primes, a result known as the Fundamental Theorem of Arithmetic. For example, $360 = 2^3 \times 3^2 \times 5$.

This calculator decomposes any integer from 2 to 1,000,000,000 into its prime factors, displays an interactive factor tree, computes the number of divisors, sum of divisors, and Euler’s totient function. Enter a second number to compute the Greatest Common Divisor (GCD) and Least Common Multiple (LCM).

The Fundamental Theorem of Arithmetic

Every integer n > 1 can be expressed uniquely (up to ordering) as a product of prime powers:

where $p_1 < p_2 < \cdots < p_k$ are distinct primes and each exponent $a_i \geq 1$. This uniqueness is what makes prime factorization the foundation for many areas of mathematics, from simplifying fractions to modern cryptography.

How to Use This Calculator

Single Number Mode

Enter any integer between 2 and 1,000,000,000. The calculator instantly shows the prime factorization in exponential notation, an interactive factor tree, all divisors, and number-theoretic properties.

Dual Number Mode (GCD & LCM)

Enter a second number to compute the Greatest Common Divisor and Least Common Multiple. A Venn diagram visualises which prime factors are shared and which are exclusive to each number.

Step-by-Step Division

Toggle Show division steps to see the trial division algorithm trace: each row shows the divisor tested, the resulting quotient, and remainder.

Reading the Factor Tree

The factor tree splits each composite number into its smallest prime divisor and the quotient, repeating until all branches end at primes. For a detailed walkthrough, the Fundamental Theorem of Arithmetic, and the trial division algorithm, see the Factor Tree guide.

Formulas and Methods

Trial Division ($6k \pm 1$)

The algorithm first divides by 2 and 3 while possible, then tests candidates of the form $6k-1$ and $6k+1$ up to $\sqrt{n}$. This skips all multiples of 2 and 3, reducing trial count by ~2/3. Time complexity: $O(\sqrt{n})$ — at most 31,623 iterations for the maximum input of $10^9$.

Number of Divisors and Sum of Divisors

$d(n) = \prod (a_i + 1)$ counts divisors; $\sigma(n)$ sums them using a geometric series formula. For the full formulas, perfect numbers, and the Euclid-Euler theorem, see the Divisor Calculator guide.

Euler’s Totient $\phi(n)$

Counts integers in [1, n] coprime to n. For a prime $p$, $\phi(p) = p - 1$. For Euler’s theorem, RSA cryptography, and worked examples, see the Euler Totient Calculator guide.

GCD and LCM via Factorization

GCD takes shared primes at minimum exponents; LCM takes all primes at maximum exponents. For the fundamental identity, practical examples, and scheduling problems, see the GCD/LCM Calculator guide.

Real-World Examples

1. Simplifying Fractions

To simplify 48/180, find GCD(48, 180). Factor: $48 = 2^4 \times 3$, $180 = 2^2 \times 3^2 \times 5$. $\gcd = 2^2 \times 3 = 12$. Divide both by 12: $48/180 = 4/15$.

2. Scheduling Problems

Two buses arrive every 12 and 18 minutes. When do they coincide?$\text{lcm}(12, 18)$: $12 = 2^2 \times 3$, $18 = 2 \times 3^2$. $\text{lcm} = 2^2 \times 3^2 = 36$ minutes.

3. Gear Ratio Simplification

Gears with 24 and 36 teeth. GCD(24, 36) = 12. Simplest ratio: 2:3.

Euler’s Totient and RSA Cryptography

Euler’s totient is the mathematical backbone of RSA encryption, the most widely used public-key cryptosystem. For the full RSA key generation process, Euler’s theorem, and security analysis, see the Euler Totient Calculator guide.

Common Misconceptions

• 1 is not prime. By convention, 1 is neither prime nor composite. Including 1 as prime would break the uniqueness of factorization.
• Not all odd numbers are prime. Examples: $9 = 3^2$, $15 = 3 \times 5$, $21 = 3 \times 7$.
• Primes are infinite. Euclid proved that no finite list of primes can be complete.
• Factorization is not the same as listing factor pairs. Prime factorization gives the unique canonical form; factor pairs (e.g., $12 = 3 \times 4 = 2 \times 6$) are not unique.

Algorithm Performance

This calculator uses trial division with $6k \pm 1$ optimisation, which runs in $O(\sqrt{n})$ time. For the maximum input of $10^9$, the algorithm tests at most $\sqrt{10^9} \approx 31{,}623$ candidates, completing in well under 100ms in any modern browser. No server-side computation is needed.

For numbers significantly larger than $10^{12}$, advanced algorithms like the Quadratic Sieve or General Number Field Sieve are needed, but these are beyond the scope of a browser-based educational tool.

Frequently Asked Questions

What is a prime number?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

How does the factor tree work?

The tree starts with your number at the top. At each level, the number is split into its smallest prime factor (left branch) and the remaining quotient (right branch). This continues until all branches end in primes.

What is GCD used for?

The Greatest Common Divisor is used to simplify fractions, find common denominators, solve Diophantine equations, and in the Euclidean algorithm. It is one of the oldest algorithms in mathematics.

Why can’t I enter numbers larger than 1 billion?

Trial division time grows with $\sqrt{n}$. For $10^9$ this takes ~31,000 steps (instant). For $10^{18}$ it would require ~$10^9$ steps, which could freeze the browser. The cap ensures consistent performance.

What is the difference between prime factorization and listing factors?

Prime factorization expresses a number as a product of primes (e.g., $12 = 2^2 \times 3$). Listing factors gives all divisors (1, 2, 3, 4, 6, 12). This calculator shows both.

Is prime factorization related to cryptography?

Yes. RSA encryption relies on the difficulty of factoring large semiprimes (products of two large primes). While this calculator handles numbers up to $10^9$ easily, factoring a 2048-bit semiprime would take billions of years with current technology.

References

• Wikipedia. “Fundamental theorem of arithmetic.” https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
• Wolfram MathWorld. “Fundamental Theorem of Arithmetic.” https://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html
• Wikipedia. “Trial division.” https://en.wikipedia.org/wiki/Trial_division
• Wikipedia. “Sieve of Eratosthenes.” https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• Wikipedia. “Integer factorization.” https://en.wikipedia.org/wiki/Integer_factorization

Disclaimer

This calculator is provided for educational purposes. While the algorithms are mathematically correct for all valid inputs, this tool is not intended for cryptographic applications. For production cryptography, use established libraries with constant-time implementations.