Factorize any integer, check primality, find GCD & LCM, and visualize the factor tree.
Prime factors shown in circles; composite nodes in rounded squares.
Type any integer from 2 to 1,000,000,000 into the Number field, or click a preset (360, 1001, 1,000,000) to load an example.
Choose from Prime Factorization, Is Prime?, GCD (Greatest Common Divisor), LCM (Least Common Multiple), or List Primes Up To N. For GCD and LCM, enter a second number too.
The result card shows the answer with step-by-step work. Switch to Factor Tree to see a visual breakdown, or All Factors for the complete list of divisors.
n = pโ^eโ ร pโ^eโ ร ... ร pโ^eโ Every integer greater than 1 can be expressed as a unique product of prime powers. This is the Fundamental Theorem of Arithmetic.
ฯ(n) = (eโ + 1)(eโ + 1)ยทยทยท(eโ + 1) Given the prime factorization n = pโ^eโ ร pโ^eโ ร โฆ ร pโ^eโ, the total number of divisors is the product of each exponent plus one.
gcd(a, b) = gcd(b, a mod b) Repeat the step gcd(a, b) = gcd(b, a mod b) until b = 0. The last non-zero remainder is the GCD.
lcm(a, b) = |a ร b| / gcd(a, b) Compute the GCD first, then divide the product of the two numbers by their GCD to get the LCM.
Test divisors d from 2 to โโnโ A number n is prime if no integer from 2 to โn divides it evenly. Trial division is O(โn) โ fast for numbers up to 10โน.
Prime factorization is used to simplify fractions, find GCDs and LCMs, solve divisibility problems, and forms the basis of RSA public-key cryptography. It also helps determine whether a number is a perfect square, perfect cube, or abundant/deficient number.
GCD (Greatest Common Divisor) is the largest integer that divides both numbers. LCM (Least Common Multiple) is the smallest integer divisible by both. They are related by: GCD ร LCM = a ร b. GCD is used to simplify fractions; LCM is used to add them.
Test whether any integer from 2 to โn divides n. If none do, n is prime. For n = 1,000,000,000, you need to check up to โ10โน โ 31,623 divisors โ fast enough to compute in milliseconds.
This calculator handles integers up to 1,000,000,000 (10โน). For prime checking and factorization, trial division up to โn is used, which is efficient for this range.
The factor tree breaks a composite number into two factors repeatedly until all branches end in prime numbers (shown in circles). The primes at the bottom of all branches are the prime factors of the original number.
A perfect number equals the sum of its proper divisors (e.g., 6 = 1+2+3). An abundant number is less than this sum (e.g., 360, where the proper divisor sum is 810). A deficient number is greater than this sum (e.g., any prime).