Recently, I’ve been working through Project Euler in order to improve my core programming skills.
One of those recurring problems requires efficiently calculating and testing for prime numbers. The first algorithm that comes to mind is The Sieve of Eratosthenes. The Sieve, is one of many prime sieves, and is a simple yet time efficient algorithm for finding all the primes below a certain limit.
- Make a table one entry for every number \(2 \leq n \leq limit\)
- Starting at 2, cross out all multiples of 2, not counting 2 itself.
- Move up to the next number ...