Sieve of Eratosthenes
A prime number is any number that can be divided evenly by 1 and itself
only. The first three primes are 2, 3, and 5. To find all of the primes
up to a particular number, use the sieve of Eratosthenes. Let's find all
of the primes up to 100. List every number from 2 to 100. Starting from
the first prime, which is 2, cross off every number going up by 2 all the
way to 100, since they can be divided evenly by 2:
Starting from the next prime, which is 3, cross off every number going up
by 3 all the way to 100, since they can be divided evenly by 3:
Skip 4 because it's crossed off. Starting from the next prime, which is
5, cross off every number going up by 5 all the way to 100, since they
can be divided evenly by 5. Continue this process until there's nothing
more to cross off:
The numbers that are not crossed off are all of the primes up to 100.