Prime Factorization Formulas

Master prime factorization with comprehensive formulas and algorithms. From the fundamental theorem of arithmetic to advanced factorization techniques.

1Fundamental Theorem of Arithmetic

The cornerstone of prime factorization - every integer greater than 1 has a unique prime factorization.

where are primes and

Key Properties:

• Uniqueness: Only one way to factorize (up to order)
• Completeness: Every integer has this representation
• Multiplicativity: Basis for GCD and LCM calculations

Example:

This is the only way to express 60 as a product of prime powers

2Trial Division Algorithm

The most basic and intuitive method for finding prime factors by systematically testing divisibility.

Algorithm Steps:

1. Initialize: Set current number n and divisor d = 2

2. Test: While d² ≤ n, check if d divides n

3. Factor: If d | n, record d and replace n with n/d

4. Increment: If d ∤ n, increment d (skip even numbers after 2)

5. Finish: If n > 1 after loop, then n is the final prime factor

Example: Factor 84

Step 1: n = 84, d = 2

84 ÷ 2 = 42 → factor: 2

Step 2: n = 42, d = 2

42 ÷ 2 = 21 → factor: 2

Step 3: n = 21, d = 3

21 ÷ 3 = 7 → factor: 3

Step 4: n = 7, d = 4

Since 4² = 16 > 7, stop

7 is prime → factor: 7

3Optimized Trial Division

Enhanced version that skips composite numbers and uses mathematical optimizations.

Optimization 1: Skip Even Numbers

After testing 2, only test odd numbers:

This reduces testing by ~50%

Optimization 2: √n Boundary

If no factor found up to √n, then n is prime:

This dramatically reduces the search space

Optimization 3: Prime-Only Testing

Only test prime divisors (requires pre-computed prime list):

Most efficient for repeated factorizations

4Complexity Analysis

Time Complexity

Basic Trial Division:

Optimized (odd only):

Prime-only testing:

Space Complexity

Basic method:

With prime list:

Practical Impact:

For n = 10⁶: ~1000 divisions needed

For n = 10¹²: ~1,000,000 divisions

5Wheel Factorization

Advanced technique that skips multiples of small primes systematically.

Wheel-2 (Skip Even Numbers)

Skip all even numbers after 2:

Skips 50% of candidates

Wheel-2,3 (Skip Multiples of 2 and 3)

Skip multiples of 2 and 3:

Skips 67% of candidates

General Wheel-W Formula

For wheel using first k primes:

Where p₁, p₂, ..., pₖ are the first k primes

6Advanced Algorithms

High-performance algorithms for factoring very large numbers.

Pollard's Rho Algorithm

Iteration Formula:

GCD Test:

Complexity: expected time

Best for: Finding factors of size 10¹⁰ to 10⁵⁰

Quadratic Sieve

Complexity:

Method: Find smooth numbers and solve linear system

Best for: Numbers with 50-100 digits

General Number Field Sieve

Complexity:

Status: Most efficient known algorithm for large composites

Best for: RSA-sized numbers (100+ digits)

7Mathematical Applications

🔢 GCD and LCM Calculation

From factorizations:

🧮 Divisor Functions

Number of divisors:

Sum of divisors:

🔐 Cryptography

• RSA Security: Based on difficulty of factoring large semiprimes

• Key Generation: Uses properties of prime factorization

• Discrete Log: Related to factorization in finite fields

📊 Number Theory

• Euler's Totient:

• Möbius Function: Depends on prime factorization structure

• Perfect Numbers: Related to Mersenne primes

Quick Reference

Common Factorizations

12=

30=

100=

360=

Algorithm Comparison

Trial Division

Best for: n < 10¹²

Pollard's Rho

Best for: 10¹² < n < 10⁵⁰

Number Field Sieve

Best for: n > 10⁵⁰

Use Prime Factorization Calculator