Prime Factorization and Divisibility Calculator
Enter a positive integer to find its prime factorization, divisors, GCD, and LCM with a second number.
Formulas Used
Prime Factorization (Trial Division):
Divide N by every integer d from 2 up to √N. Each time d divides N, record it and divide N by d. Any remainder > 1 is itself prime.
N = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ
Number of Divisors:
τ(N) = (e₁ + 1)(e₂ + 1) … (eₖ + 1)
Sum of Divisors:
σ(N) = ∏ᵢ (pᵢ^(eᵢ+1) − 1) / (pᵢ − 1)
Perfect Number:
N is perfect when σ(N) = 2N (i.e., the sum of proper divisors equals N).
GCD (Euclidean Algorithm):
gcd(a, b) = gcd(b, a mod b), base case gcd(a, 0) = a
LCM:
lcm(N, M) = (N × M) / gcd(N, M)
Assumptions & References
- N and M must be positive integers (1 – 1,000,000,000).
- Trial division is used; it is efficient for numbers up to ~10⁹ since √10⁹ ≈ 31,623 iterations.
- All divisors are listed only when τ(N) ≤ 200 to keep the output readable.
- Divisibility rules for 2–13 follow standard number-theory definitions.
- Known perfect numbers within range: 6, 28, 496, 8128, 33550336.
- Reference: Hardy & Wright, An Introduction to the Theory of Numbers, Oxford University Press.
- Divisibility rules reference: Niven, Zuckerman & Montgomery, An Introduction to the Theory of Numbers.