Prime Numbers

When to Use

Use this skill when working on prime-numbers problems in graph number theory.

Decision Tree

1. Primality testing hierarchy

   • Trial division: O(sqrt(n)), exact
   • Miller-Rabin: O(k log^3 n), probabilistic
   • AKS: O(log^6 n), deterministic polynomial

2. Factorization

   • Trial division for small factors
   • Pollard's rho: probabilistic, medium numbers
   • Quadratic sieve: large numbers
   • sympy_compute.py factor "n"

3. Prime distribution

   • Prime Number Theorem: pi(x) ~ x/ln(x)
   • Prime gaps: p_{n+1} - p_n
   • sympy_compute.py limit "pi(x) * ln(x) / x"

4. Fermat's Little Theorem

   • a^{p-1} = 1 (mod p) for a not divisible by p
   • Use for modular exponentiation