Algorithms / Primes Sieves Factorization
Least You Need to Know: Primes, Sieves, Trial Division, and Factorization Bounds
Prime-heavy interview questions usually boil down to one of three facts: every composite has a small factor, every integer has a unique prime factorization, and sieve-style preprocessing trades memory for many fast primality or factor queries.
The least you need to know
- A composite number has a prime factor at most its square root.
- Trial division only needs to test divisors up to `sqrt(n)`.
- The sieve of Eratosthenes marks multiples of each prime and starts at `p^2`.
- Unique prime factorization is the reason gcd/lcm and divisor counting formulas work cleanly.
- Prime preprocessing is worth it when many related queries share the same bound.
Key notation
prime
integer greater than `1` with exactly two positive divisors
spf(n)
smallest prime factor of `n`
sqrt(n)
threshold for trial-division checks
Tiny worked example
- To test whether `91` is prime, try prime divisors up to `sqrt(91)`.
- Since `sqrt(91)` is less than `10`, checking `2, 3, 5, 7` is enough.
- Finding `7 * 13 = 91` shows the number is composite without any larger checks.
Common mistakes
- Students sometimes keep testing divisors above `sqrt(n)` even though the factor-pair argument already covers them.
- In a sieve, marking from `2p` is correct but wastes work because smaller primes already handled earlier multiples.
- A number being odd does not make it prime.
How to recognize this kind of problem
- The task asks many primality, factor-count, or smallest-factor queries under one shared limit.
- A direct check is acceptable for one number, but repeated checks want a sieve or SPF table.
- The explanation needs a factor-pair bound rather than brute-force enumeration.