Sieve of Eratosthenes

A prime number is a whole number that has exactly two factors, 1 and itself.

We can use the Sieve of Eratosthenes to find out whether a number is prime or composite.

The following example illustrates how the Sieve of Eratosthenes, can be used to find all the prime numbers that are less than 100.

Step 1: Write the numbers 1 to 100 in ten rows.

Step 2: Cross out 1 because 1 is not a prime.

Step 3: Circle 2 and cross out all multiples of 2. (2, 4, 6, 8, 10, ...)

Step 4: Circle 3 and cross out all multiples of 3. (3, 6, 9, 12, 15, ...)

Step 5: Circle 5 and cross out all multiples of 5. (5, 10, 15, 20, ...)

Step 6: Circle 7 and cross out all multiples of 7. (7, 14, 21, 28, ...)

Circle all the numbers that are not crossed out and they are the prime numbers less than 100.

The following video describes how to use the Sieve of Eratosthenes to find all the prime numbers less than 100.

Custom Search