Enter a positive integer to decompose into prime factors with step-by-step trial division
Result
Input
Prime Factors
Step-by-Step Breakdown
Prime Factorization Method
Fundamental Theorem of Arithmetic:
Any integer n > 1 can be uniquely expressed as:
n = p₁a₁ × p₂a₂ × … × pkak
where p₁ < p₂ < … < pk are all prime numbers
Prime factorization is one of the most fundamental concepts in number theory, essential for understanding integer structure, computing GCD, and evaluating Euler's totient function.
⚠This tool uses trial division: first divide by 2, then by 3, 5, 7, ... up to √n. Each division step is shown in real time during factorization.
What Is Prime Factorization?
Prime factorization represents a composite number as a product of prime numbers. It is a fundamental concept in number theory. According to the Fundamental Theorem of Arithmetic, every integer greater than 1 has a unique prime factorization.
Fundamental Theorem
Every integer greater than 1 can be uniquely expressed as a product of primes in ascending order. This is the core theorem of integer theory.
Prime & Composite
A prime number is >1 and divisible only by 1 and itself. A composite number has additional divisors. 1 is neither prime nor composite.
Trial Division
Test divisibility by primes from smallest to largest up to √n. If divisible, record that prime and continue dividing, then try the next.
Applications
Prime factorization is the mathematical basis of RSA encryption, and is also used for GCD computation, Euler totient, and congruence solving.
RSA EncryptionPublic-Key CryptographyGCD/LCMEuler TotientCompetition Math
Frequently Asked Questions
What is prime factorization?▼
Prime factorization expresses a composite number as a product of prime numbers. For example, 12 = 2² × 3, 360 = 2³ × 3² × 5. By the Fundamental Theorem of Arithmetic, every integer greater than 1 has a unique prime factorization.
What are prime and composite numbers?▼
A prime number is greater than 1 and divisible only by 1 and itself (e.g., 2,3,5,7,11). A composite number has additional divisors (e.g., 4,6,8,9,10). 1 is neither prime nor composite.
What is prime factorization used for?▼
Prime factorization is the foundation of number theory: RSA encryption, GCD/LCM computation, Euler totient calculation, and congruence equation solving.
How to quickly test if a number is prime?▼
Use trial division up to √n. If n is not divisible by any integer from 2 to √n, it is prime. For 37, test 2,3,4,5,6 — none divide evenly → 37 is prime.
Free online calculators and tools covering mathematics, unit conversion, text processing, and daily life. Accurate, fast, mobile-friendly, and completely free to use.