CalculateY
Quick Answer
The prime factorization of 84 is 2^2 x 3 x 7, giving it 12 total positive divisors.
Common Examples
| Input | Result |
|---|---|
| 60 | 2^2 x 3 x 5 (12 divisors) |
| 97 | 97 (prime number, 2 divisors) |
| 360 | 2^3 x 3^2 x 5 (24 divisors) |
| 1000 | 2^3 x 5^3 (16 divisors) |
| 17 | 17 (prime number, 2 divisors) |
How It Works
The Formula
Prime factorization decomposes a positive integer n into a product of prime numbers:
n = p1^a1 x p2^a2 x … x pk^ak
where p1 < p2 < … < pk are prime numbers and a1, a2, …, ak are their respective exponents.
The trial division algorithm works by testing each potential factor starting from 2:
- Divide n by 2 as many times as possible, counting the exponent.
- Try each odd number from 3 upward, dividing n as many times as possible.
- Stop when the trial divisor exceeds the square root of the remaining value.
- If anything remains greater than 1, it is the final prime factor.
The key optimization is that you only need to test divisors up to the square root of n. If n has no factor less than or equal to sqrt(n), then n itself is prime.
Counting total divisors: If the factorization is n = p1^a1 x p2^a2 x … x pk^ak, then the total number of positive divisors is:
d(n) = (a1 + 1) x (a2 + 1) x … x (ak + 1)
This works because each divisor is formed by choosing an exponent from 0 to ai for each prime pi.
Worked Example
To factorize 360: start dividing by 2. 360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45. So 2 appears with exponent 3. Next, try 3: 45 / 3 = 15, 15 / 3 = 5. So 3 appears with exponent 2. Next, try 5: 5 / 5 = 1. So 5 appears with exponent 1. The factorization is 2^3 x 3^2 x 5.
Total divisors = (3 + 1) x (2 + 1) x (1 + 1) = 4 x 3 x 2 = 24. The 24 divisors of 360 are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360.