GCD Calculator
Calculate the Greatest Common Divisor (GCD) of two or more numbers using the Euclidean algorithm. Also known as GCF or HCF.
Prime Factorization Calculator
Find the prime factorization of any positive integer. Breaks down numbers into their prime factors using trial division.
Prime Factorization⧉
2^3 × 3^2 × 5
3 distinct prime(s)
Is Prime?⧉
No
Composite number
Number of Divisors⧉
24.00
Total factors including 1 and n
Sum of Divisors⧉
1,170.00
σ(360)
Euler's Totient⧉
96.00
φ(n) — coprime integers < n
Input Number⧉
360.00
2^3 × 3^2 × 5
Factor Breakdown
2
×3
3
×2
5
×1
Planning notes, formulas, and examples
About the Prime Factorization Calculator
The Prime Factorization Calculator decomposes any positive integer into its unique product of prime numbers. Every integer greater than 1 is either prime or can be expressed as a product of primes — this is the Fundamental Theorem of Arithmetic.
The calculator uses trial division, testing divisibility by 2, then 3, then successive odd numbers up to the square root. For example, 360 = 2³ × 3² × 5. The factorization is unique regardless of the order of division.
Prime factorization is used to find GCD and LCM, simplify fractions and radicals, solve number theory problems, and understand the structure of numbers. It is also the mathematical foundation of RSA encryption.
When This Page Helps
Finding prime factors by hand is tedious for large numbers. This calculator factors numbers directly and shows the complete decomposition with exponents.
How to Use the Inputs
- Enter a positive integer.
- The calculator finds all prime factors by trial division.
- View the factorization in exponential form.
- See the list of individual factors.
- Use the factors for GCD, LCM, or simplification tasks.
Formula used
Trial Division: divide n by 2 repeatedly, then by 3, 5, 7, ... up to √n.
Each time n is divisible, record the prime factor and divide.
Continue until n = 1.Example Calculation
Result: 2³ × 3² × 5
360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. Factors: 2³ × 3² × 5.
Tips & Best Practices
- Every positive integer > 1 has a unique prime factorization.
- The largest prime factor is always ≤ √n (unless n itself is prime).
- For GCD: take the minimum power of each shared prime.
- For LCM: take the maximum power of each prime across both numbers.
- Numbers with many small prime factors are called "smooth numbers."
The Fundamental Theorem of Arithmetic
Every integer greater than 1 either is a prime or can be uniquely represented as a product of primes (up to ordering). This theorem is the foundation of number theory and underpins many areas of mathematics.
Smooth Numbers
A number whose prime factors are all small is called "smooth." For example, 1,000,000 = 2⁶ × 5⁶ is 5-smooth. Smooth numbers are important in cryptographic algorithms and integer factorization methods.
Factor Trees
In education, factor trees visually break down numbers by repeatedly splitting composites into two factors until all leaves are prime. While helpful for learning, the trial division algorithm is more systematic and efficient.
Sources & Methodology
Last updated:
Frequently Asked Questions
It is the process of expressing a number as a product of prime numbers. For example, 84 = 2² × 3 × 7. Every positive integer has a unique prime factorization.
A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23.
1 is excluded from the primes by convention to preserve the uniqueness of prime factorization. If 1 were prime, 12 could be factored as 2²×3 or 1×2²×3, violating uniqueness.
RSA encryption relies on the difficulty of factoring large semiprimes (products of two large primes). While easy to multiply primes together, reversing the process for 200+ digit numbers is computationally infeasible.
As of 2024, the largest known prime is a Mersenne prime with over 41 million digits. Such primes are found using specialized algorithms, not trial division.
This calculator works well for numbers up to billions. For extremely large numbers, advanced algorithms like Pollard's rho or the quadratic sieve are needed.
More in this topic
LCM Calculator
Calculate the Least Common Multiple (LCM) of two numbers using the GCD method. Formula: LCM(a,b) = |a×b| / GCD(a,b).
Prime Number Checker
Check if any number is prime using trial division up to its square root. Determine primality and see the smallest factor if composite.