CalcMountain

Prime Factorization Calculator

Break down any positive integer into its prime factors. Shows the complete prime factorization, the number of factors, and whether the number is prime.

Prime factorization breaks any integer into its prime building blocks. Every integer greater than 1 can be written uniquely as a product of prime numbers — this is the Fundamental Theorem of Arithmetic, one of the most beautiful results in mathematics. Knowing the prime factorization of a number tells you nearly everything about its arithmetic properties.

A **prime** is a natural number greater than 1 with no divisors other than 1 and itself: 2, 3, 5, 7, 11, 13, 17, ... Every other natural number is **composite** — built from smaller primes through multiplication. So 12 = 2 × 2 × 3 = 2² × 3 (prime factorization). 100 = 2² × 5². 360 = 2³ × 3² × 5.

Prime factorizations enable many useful calculations: - **GCF**: lowest powers of common primes. - **LCM**: highest powers of all primes appearing in either number. - **Divisor counting**: from the factorization. - **Reducing fractions**: divide numerator and denominator by GCF. - **Square roots of integers**: separate squared factors.

Finding prime factorizations is computationally easy for small numbers but provably hard for very large numbers — this hardness underlies RSA cryptography, the foundation of internet security. Computers can factor 50-digit numbers, but 1000-digit semiprimes are practically impossible — secret bank transactions stay secret.

Common applications: simplifying fractions, finding GCF/LCM, number theory, cryptography (RSA, primality tests), computer science (hash functions), and any context involving divisibility properties.

Inputs

Results

Prime Factorization

2 x 2 x 2 x 3 x 3 x 5

Exponent Form

2^3 x 3^2 x 5

Is Prime?

No

Total Number of Divisors

24

Last updated:

Formula

**Prime factorization algorithm (trial division):** 1. Try smallest prime (2). Divide n while divisible. 2. Move to next prime (3, 5, 7, ...). Divide while divisible. 3. Continue until quotient = 1 or remaining quotient is itself prime. **Worked example: 360** 360 / 2 = 180 180 / 2 = 90 90 / 2 = 45 (no longer divisible by 2) 45 / 3 = 15 15 / 3 = 5 (no longer divisible by 3) 5 / 5 = 1. So 360 = 2³ × 3² × 5. **Worked example: 84** 84 / 2 = 42 42 / 2 = 21 21 / 3 = 7 7 / 7 = 1. 84 = 2² × 3 × 7. **First primes (memorize):** 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ... Up to 100: 25 primes. **Divisibility tests** (speed up trial division): | Divisor | Test | |---|---| | 2 | Last digit even | | 3 | Digit sum divisible by 3 | | 4 | Last two digits divisible by 4 | | 5 | Last digit 0 or 5 | | 6 | Divisible by both 2 and 3 | | 8 | Last three digits divisible by 8 | | 9 | Digit sum divisible by 9 | | 10 | Last digit 0 | | 11 | Alternating sum divisible by 11 | **Worked example: 9876:** Digit sum: 9+8+7+6 = 30 (divisible by 3). So 9876/3 = 3292. Digit sum of 3292: 16 (not divisible by 3). Try 2: 3292/2 = 1646. 1646/2 = 823. 823: digit sum 13 (not /3), not ending in 0 or 5, not /7 (823/7 ≈ 117.6), not /11 (8-2+3 = 9), not /13 (823/13 ≈ 63.3), not /17, not /19, not /23 (= 35.8), 823/29 = 28.4. Since 29² = 841 > 823, 823 is prime. So 9876 = 2² × 3 × 823. **Counting divisors:** For n = p₁^a × p₂^b × p₃^c × ...: Number of divisors = (a+1) × (b+1) × (c+1) × ... For 360 = 2³ × 3² × 5: Divisors = (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. So 360 has 24 divisors total. **Sum of divisors:** σ(n) = product of (p^(a+1) - 1)/(p - 1) for each prime power. For 360: 2³: (16-1)/1 = 15 3²: (27-1)/2 = 13 5¹: (25-1)/4 = 6 σ(360) = 15 × 13 × 6 = 1170. **Perfect numbers:** Numbers where sum of proper divisors equals the number: 6, 28, 496, 8128, ... 6 = 1 + 2 + 3. 28 = 1 + 2 + 4 + 7 + 14. All known perfect numbers are even (Euclid-Euler theorem), of form 2^(p-1) × (2^p - 1) where (2^p - 1) is Mersenne prime. **Common prime factorizations:** | n | Prime factorization | |---|---| | 12 | 2² × 3 | | 24 | 2³ × 3 | | 30 | 2 × 3 × 5 | | 36 | 2² × 3² | | 60 | 2² × 3 × 5 | | 100 | 2² × 5² | | 144 | 2⁴ × 3² | | 360 | 2³ × 3² × 5 | | 720 | 2⁴ × 3² × 5 | | 1000 | 2³ × 5³ | | 5040 | 2⁴ × 3² × 5 × 7 | **GCF from prime factorizations:** GCF = product of lowest powers of common primes. For 360 = 2³ × 3² × 5 and 144 = 2⁴ × 3²: Common primes: 2 and 3. Lowest powers: 2³ and 3². GCF = 2³ × 3² = 72. **LCM from prime factorizations:** LCM = product of highest powers of all primes appearing. For 360 and 144: Highest 2: 2⁴. Highest 3: 3². Highest 5: 5¹ (in 360 only). LCM = 2⁴ × 3² × 5 = 720. **Connection: GCF × LCM = product of numbers.** For 360 and 144: GCF × LCM = 72 × 720 = 51,840 = 360 × 144 ✓. **Square roots of perfect squares:** If n = p₁^(2a) × p₂^(2b) × ... (all even powers), then √n is integer. 100 = 2² × 5². √100 = 2 × 5 = 10. 900 = 2² × 3² × 5². √900 = 2 × 3 × 5 = 30. If any power is odd: √n is irrational. **Simplifying square roots:** √72 = √(2³ × 3²) = 2 × 3 × √2 = 6√2. Pull out paired primes; leave unpaired under the radical. **Square-free numbers:** Numbers where no prime appears more than once. Examples: 6 = 2 × 3, 30 = 2 × 3 × 5, 105 = 3 × 5 × 7. Density: about 6/π² ≈ 60.8% of all integers. **Algorithms for large numbers:** Trial division: works up to ~10^15 in reasonable time. For larger numbers: - **Pollard's rho**: fast for finding small factors of large numbers. - **Quadratic sieve, GNFS** (General Number Field Sieve): fastest known for very large numbers. - **Quantum (Shor's algorithm)**: exponentially faster on quantum computers (not yet practical scale). For typical use cases (numbers < 10^12), trial division by primes up to √n works fast. **Primes are infinite:** Euclid proved (300 BC) infinitely many primes exist. If only finitely many primes p₁, p₂, ..., pₙ existed, consider N = p₁ × p₂ × ... × pₙ + 1. N has no factor among the finite primes, so must be prime itself (or have prime factor not in list). Contradiction. **Prime gaps:** Distance between consecutive primes varies enormously: - (3, 5) gap 2 (twin primes). - (89, 97) gap 8. - (113, 127) gap 14. - Large gaps exist for any length (proof: k! + 2, k! + 3, ..., k! + k all composite). Twin prime conjecture (open): infinitely many primes with gap 2. **RSA cryptography:** RSA security relies on factoring being hard. Generate two large primes p, q (say 1024 bits each). Public modulus n = p × q. Encryption uses n; decryption uses p, q. Anyone with n must factor it to break the code. With 2048-bit n, factoring takes ~thousands of years on best computers — practically impossible. Quantum computers (when scalable) could break this via Shor's algorithm — drives current research in post-quantum cryptography. **Mersenne primes:** Primes of form 2^p - 1 where p is also prime. Examples: M₂ = 2² - 1 = 3 (prime). M₃ = 2³ - 1 = 7 (prime). M₅ = 2⁵ - 1 = 31 (prime). M₇ = 127 (prime). M₁₃ = 8191 (prime). Largest known prime (2024): M₈₂₅₈₉₉₃₃ = 2^82,589,933 - 1, with 24,862,048 digits. Discovered via GIMPS (Great Internet Mersenne Prime Search) distributed computing. **Common applications:** - **Number theory**: foundation of integer arithmetic. - **Fraction simplification**: GCF via prime factorization. - **LCM**: lowest common denominator. - **Cryptography**: RSA, modular arithmetic. - **Hash functions**: prime numbers in hash design. - **Computer science**: pseudorandom generators, primality testing. - **Coding theory**: error correction codes. **Software:** - **Python**: sympy.factorint(n) returns factor dict. - **Wolfram Alpha**: factor any integer. - **JavaScript**: manual implementation typical. - **Online calculators**: for casual use. - **PARI/GP**: number theory specialist. **Computational complexity:** For n-bit integer, classical best algorithms run in exp(O(n^(1/3))) time — sub-exponential but slow. This is the basis of RSA security: factoring 2048-bit semiprimes (1024-bit primes each) takes longer than the age of the universe with classical computers. **Pitfalls:** - **1 is not prime**: special case. - **Order doesn't matter**: 12 = 2² × 3, not 3 × 2². - **Each prime power**: 2² is 4, not "2 to the 2" misread. - **Largest prime factor**: just one of multiple. - **For very large numbers**: trial division too slow.

How to use this calculator

  1. Enter a positive integer ≥ 2.
  2. Calculator returns prime factorization (with exponents).
  3. For very large numbers: may be slow with simple algorithms.
  4. Use for: GCF, LCM, fraction simplification, divisor counting.
  5. Verify: multiply factors together to get original.
  6. For primes: factorization is the number itself.

Worked examples

Standard composite

**Scenario:** Factor 360. **Calculation:** 360 = 2³ × 3² × 5. Steps: 360/2 = 180, 180/2 = 90, 90/2 = 45, 45/3 = 15, 15/3 = 5, 5/5 = 1. **Result:** 2³ × 3² × 5. Number of divisors: (3+1)(2+1)(1+1) = 24. Sum of divisors: 1170. 360 is highly composite — many factors make it useful in calendar systems and rotation degrees.

Recognizing a prime

**Scenario:** Is 97 prime? **Calculation:** Test divisibility by primes up to √97 ≈ 9.85: 2, 3, 5, 7. 97/2 not whole. 97/3 = 32.33 not whole. 97/5 = 19.4 not whole. 97/7 = 13.86 not whole. So 97 has no prime divisors ≤ √97, therefore prime. **Result:** 97 is prime. Only divisors: 1 and 97. To prove a number is prime: trial divide by all primes up to √n. If none divide, the number is prime.

Large number factoring

**Scenario:** Factor 999. **Calculation:** 999/3 = 333. 333/3 = 111. 111/3 = 37. 37 is prime (not divisible by primes < √37 ≈ 6.1, i.e., 2, 3, 5). So 999 = 3³ × 37. **Result:** 999 = 3³ × 37 = 27 × 37. Useful: GCF(999, 100) = 1 (coprime), LCM(999, 100) = 99,900. Divisor count: (3+1)(1+1) = 8.

When to use this calculator

**Use prime factorization for:**

- **Simplifying fractions**: divide by GCF. - **Finding GCF**: common prime powers. - **Finding LCM**: union of prime powers. - **Simplifying square roots**: pull out paired primes. - **Counting divisors**: from factorization exponents. - **Number theory problems**: divisibility properties. - **Cryptography understanding**: foundation of RSA.

**Key methods:**

- **Trial division**: divide by primes up to √n. - **Factor tree**: visual breakdown. - **Sieve**: list primes first, then divide.

For small numbers (n < 1000): trial division by hand is feasible. For larger numbers: use a calculator or computer.

**Divisibility shortcuts:**

| Divisor | Quick test | |---|---| | 2 | Even (last digit 0,2,4,6,8) | | 3 | Digit sum /3 | | 5 | Ends in 0 or 5 | | 9 | Digit sum /9 | | 11 | Alternating digit sum /11 | | 7 | More complex; use long division |

**Practical examples:**

- **GCF(48, 36)**: 48 = 2⁴ × 3, 36 = 2² × 3². GCF = 2² × 3 = 12. - **LCM(48, 36)**: 2⁴ × 3² = 144. - **Simplify 48/36**: divide by GCF (12): 4/3. - **Divisor count of 720**: 720 = 2⁴ × 3² × 5. Count = 5×3×2 = 30.

**Square root simplification:**

√72 = √(2³ × 3²) = √(2² × 2 × 3²) = 2 × 3 × √2 = 6√2.

Pull out paired primes; leave unpaired under radical.

**Common applications:**

- **Math education**: foundational number theory. - **Algebra**: factoring polynomials uses similar concepts. - **Computer science**: hash design, RSA cryptography. - **Cryptography**: RSA, Diffie-Hellman key exchange. - **Engineering**: divisibility for synchronization. - **Music**: rational frequency ratios. - **Calendar systems**: 60 = 2² × 3 × 5 (highly divisible).

**Why some numbers are special:**

- **Highly composite**: 360 (many divisors). - **Powers of 2**: 1024 = 2¹⁰ (computer-friendly). - **Prime**: only 1 and self (cryptography). - **Mersenne primes**: 2^p - 1 (record-setting primes). - **Perfect numbers**: equal to sum of proper divisors.

**Pitfalls:**

- **1 is not prime**: by convention. - **Negative numbers**: technically integers, factorization extends with sign. - **Very large numbers**: factorization becomes computationally hard. - **Confusing prime with composite**: prime has only 1 and itself; composite has more. - **Forgetting all factors**: write each prime to its highest power. - **For zero**: undefined (0 = 2 × 0 = 3 × 0 = ...).

**Software:**

- **Python**: sympy.factorint(n) returns dict of prime: power. - **Wolfram Alpha**: type "factor 360" for instant result. - **Online calculators**: many available, instant for typical numbers. - **Mathematica**: FactorInteger[n]. - **PARI/GP**: factor(n).

**Computational limits:**

- 10^15: trial division still works in seconds. - 10^20: needs Pollard's rho or QS. - 10^100+: GNFS (General Number Field Sieve), takes years. - 10^200+ (cryptographic): essentially infeasible.

**Educational notes:**

Prime factorization typically taught in 5th-6th grade. Foundation for: - Fractions (simplification, common denominators). - Algebra (polynomial factoring). - Number theory. - Cryptography (high school CS or college).

Visual aids: factor trees, Venn diagrams for GCF/LCM.

**Pitfalls:**

- **1 = not prime**: by mathematical convention. - **Order of factors**: doesn't matter (commutative). - **For 0**: undefined. - **Negative**: -360 = -1 × 2³ × 3² × 5 (with sign). - **For factorization beyond integers**: needs algebraic number theory. - **Mistaking a number for prime when not**: always check all primes ≤ √n.

Common mistakes to avoid

  • Treating 1 as prime (it's not by convention).
  • Forgetting to check all primes up to √n for primality test.
  • Missing factors (e.g., 12 = 2² × 3, not just 2 × 6).
  • Mixing up GCF and LCM (different combinations of factorizations).
  • For square root simplification: not pulling out all paired primes.
  • For composite testing: stopping divisibility tests too early.
  • Forgetting 2 (smallest prime).
  • For very large numbers: trying trial division when faster methods exist.

Frequently Asked Questions

Sources & further reading

SponsoredShop Top Deals on AmazonSupport CalcMountain — browse top-rated products at no extra cost to you.

Related Calculators

Greatest Common Factor Calculator

Find the greatest common factor (GCF) of two numbers.

Least Common Multiple Calculator

Find the least common multiple (LCM) of two numbers.