Find prime factorization of any positive integer with step-by-step trial division table and interactive factor tree canvas. Also shows all divisors, GCD and LCM of two numbers, and detects whether the input is prime or composite.
Type any positive integer. The tool immediately shows whether it is prime or composite, and begins the factorization. For the GCD/LCM feature, enter a second number in the optional second field.
The trial division table shows each step: the current number, the smallest prime divisor tried, the quotient, and the remainder. The process continues until the quotient is 1. The final factorization is shown in index notation (e.g. 360 = 2³ × 3² × 5).
The factor tree canvas visually splits the number into its prime factors, branching like a tree. Below the tree, all divisors of the number are listed in order. If you entered a second number, the GCD (Euclidean algorithm steps shown) and LCM are also computed.
Prime factorization (prime decomposition) expresses a composite number as a product of prime numbers. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has a unique prime factorization (up to order). For example: 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. This is the basis of number theory and has applications in cryptography (RSA encryption relies on the difficulty of factoring large numbers), simplifying fractions, and finding GCD/LCM.
Trial division tests each prime number starting from 2 as a potential factor. If the prime divides the number evenly (no remainder), divide it out and record it. Continue with the quotient. If no prime up to √n divides n, then n is prime. Efficiency: you only need to test primes up to √n because if n has a factor larger than √n, it must also have one smaller than √n. For n = 100: test 2 (100/2=50), 2 (50/2=25), 5 (25/5=5), 5 (5/5=1) → 100 = 2² × 5².
The Euclidean algorithm finds the Greatest Common Divisor (GCD) by repeatedly applying: GCD(a, b) = GCD(b, a mod b) until b = 0, at which point GCD = a. Example: GCD(48, 18): GCD(48,18) → GCD(18,12) → GCD(12,6) → GCD(6,0) → GCD = 6. This is far more efficient than factoring both numbers. LCM(a,b) = (a×b)/GCD(a,b). The Euclidean algorithm runs in O(log min(a,b)) steps — extremely fast even for large numbers.
Given prime factorizations of a and b: GCD takes the minimum power of each prime factor. LCM takes the maximum power of each prime factor. Example: 12 = 2²×3, 18 = 2×3². GCD(12,18) = 2^min(2,1) × 3^min(1,2) = 2¹×3¹ = 6. LCM(12,18) = 2^max(2,1) × 3^max(1,2) = 2²×3² = 36. Verification: GCD×LCM = 6×36 = 216 = 12×18 ✓. This relationship (GCD×LCM = a×b) always holds for any two positive integers.
The tool uses trial division, which is efficient for numbers up to about 10^12 (1 trillion). For very large numbers (15+ digits), factorization may take a moment because trial division tests all primes up to √n. The tool tests primes up to 10^6, handling all composites whose smallest prime factor is ≤ 10^6. Numbers beyond this range that remain after trial division are reported as likely prime. For cryptographic-strength factorization of 2048-bit numbers, specialized algorithms (quadratic sieve, general number field sieve) running on supercomputers are required.
Factoring large numbers is computationally hard — no known algorithm runs in polynomial time. The best known classical algorithm (General Number Field Sieve) factors an n-bit number in roughly exp(O(n^(1/3))). For a 2048-bit RSA number, this requires more computation than humanity can currently achieve. This hardness is the security basis of RSA encryption: everyone can multiply two large primes quickly, but recovering the primes from their product is infeasible. Quantum computers (Shor's algorithm) would break RSA in polynomial time, which is why post-quantum cryptography is actively researched.
