Algorithm: Test divisibility by all
integers from 2 to √n

def is_prime(n):
  if n < 2: return False
  if n < 4: return True
  if n % 2 == 0 or n % 3 == 0:
    return False
  i = 5
  while i * i <= n:
    if n % i == 0 or n % (i+2) == 0:
      return False
    i += 6
  return True

Why only test up to √n?
  If n = a × b, then min(a,b) ≤ √n
  So if no factor ≤ √n, n is prime

Complexity: O(√n)
  For n = 1,000,000 → test ~1000 values
  Practical for n up to ~10¹²

Trial division is the simplest primality test. The optimization of testing only 6k±1 (skipping multiples of 2 and 3) reduces checks by 67%. Sufficient for everyday use.

Find ALL primes up to N:

1. List numbers 2, 3, 4, ..., N
2. Start with smallest (2)
3. Mark all multiples of 2 as composite
4. Move to next unmarked number (3)
5. Mark all multiples of 3
6. Repeat until √N reached
7. Remaining unmarked = PRIMES

Sieve of Eratosthenes (up to 30):
  2  3  4̶  5  6̶  7  8̶  9̶  10̶
  11 12̶ 13 14̶ 15̶ 16̶ 17 18̶ 19
  20̶ 21̶ 22̶ 23 24̶ 25̶ 26̶ 27̶ 28̶
  29 30̶

Primes: 2,3,5,7,11,13,17,19,23,29

Complexity: O(n log log n)
Memory: O(n) → segmented for large n

The Sieve of Eratosthenes (240 BC) is still one of the fastest algorithms for generating all primes up to N. For primes below 10⁹, segmented sieves run in seconds on modern hardware.

Probabilistic primality test:
  'Probably prime' or 'definitely composite'

Basis: Fermat's Little Theorem
  If p is prime: a^(p-1) ≡ 1 (mod p)

Miller-Rabin extends this:
  Write n−1 = 2ˢ × d (d odd)
  Choose random witness a
  Compute a^d mod n
  If = 1 or n−1: probably prime
  Square up to s−1 times:
    If any = n−1: probably prime
  Otherwise: COMPOSITE (certain)

Error probability: ≤ (1/4)^k
  k witnesses → P(error) ≤ 4⁻ᵏ
  20 witnesses → P(error) < 10⁻¹²

Deterministic variant:
  Test a = 2,3,5,7,11,13,17,19,23,29,31,37
  Correct for all n < 3.317×10²⁴

Miller-Rabin is the standard primality test in practice. With enough witnesses, false positives are astronomically unlikely. Most crypto libraries use Miller-Rabin with 40+ rounds for key generation.

Express n as product of primes:

Trial Division Factorization:
  360 ÷ 2 = 180
  180 ÷ 2 = 90
  90  ÷ 2 = 45
  45  ÷ 3 = 15
  15  ÷ 3 = 5
  5   ÷ 5 = 1
  360 = 2³ × 3² × 5

Applications:
  GCD(a,b): min of each prime power
  LCM(a,b): max of each prime power
  GCD(12,18) = GCD(2²×3, 2×3²)
             = 2¹×3¹ = 6
  LCM(12,18) = 2²×3² = 36

Number of divisors:
  n = p₁^a₁ × p₂^a₂ × ...
  d(n) = (a₁+1)(a₂+1)...
  360 = 2³×3²×5¹
  d(360) = 4×3×2 = 24 divisors

Cryptographic factoring:
  RSA-2048: ~617 digit number
  No known efficient algorithm!

Factoring large numbers is computationally hard — this is the foundation of RSA encryption. If quantum computers achieve sufficient scale, Shor's algorithm could factor in polynomial time, breaking RSA.