Sign in to watch this lesson
Algorithms - Bits and Number Theory · 4:25
Integer Factorization by Trial Division
Trial division tries divisors in order while d squared still fits under n, divides each one out as often as it goes, and reports whatever is left above 1 as a prime. We watch the square-root ceiling drop on 360 and collapse on 4817191, find the worst cases, then cut the candidates with odd numbers, the 2*3*5 wheel and pre-sieved primes (measured on this Mac), and finish with the smallest-prime-factor table from the linear sieve, which factors any number up to N in a logarithmic number of hops.
You will learn
- Factor n by trial division in O(sqrt(n)), dividing out each factor fully and reporting the leftover prime
- Explain why every divisor found is prime and why the loop may stop once d * d > n
- Cut the constant factor with odd-only steps, the 2*3*5 wheel and pre-sieved primes, and know the worst-case inputs
- Build a smallest-prime-factor table with the linear sieve and factor many numbers in O(log n) each