Sign in to watch this lesson
Algorithms - Bits and Number Theory · 4:50
Sieve of Eratosthenes
Instead of testing each number for divisors, let every prime cross out its own multiples. On the 1..16 grid we see the wasted double marks, then start each prime at its square and stop at the square root of n, which brings the work down to about n log log n. Measured on this Mac at n = 10^8, the segmented sieve that works one L1-sized block at a time runs more than five times faster than the plain byte array, and the same block idea finds the primes in a window far from zero.
You will learn
- Implement the Sieve of Eratosthenes starting each prime at p*p and stopping at sqrt(n), avoiding the int overflow and the 0/1 pitfalls
- Explain why the sieve does about n ln ln n marks (the sum of 1/p over primes)
- Explain why memory layout dominates the running time, and when bits, bytes and segmented blocks win
- Use a segmented sieve with base primes up to sqrt(R) to list the primes in a window [L, R] with R up to 10^12