The Sieve of Eratosthenes is a super efficient way to determine whether or not numbers are prime. Essentially, it takes a max number, and via the process of elimination, gives you an array that contains every prime number up to that max number.
The very short explanation is this:
- Create an array from 0..max
- Starting at 2, delete every multiple of 2 from the array.
- Then, go back to the beginning, and delete every multiple of 3.
- Repeat this starting from the next available number at the beginning of the array.