Keil Logo

Sieve of Eratosthenes

The Sieve of Eratosthenes is a standard benchmark used to determine the relative speed of different computers or, in this case, the efficiency of the code generated for the same computer by different compilers. The sieve algorithm was developed in ancient Greece and is one of a number of methods used to find prime numbers. The sieve works by a process of elimination using an array that starts with 2 and keeps all the numbers in position. The process is:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Starting after 2, eliminate all multiples of 2.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Starting after 3, eliminate all multiples of 3.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Starting after 5, eliminate all multiples of 5.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Continue until the next remaining number is greater than the square root of the largest number in the original series. In this case, the next number, 7, is greater than the square root of 25, so the process stops. The remaining numbers are all prime.

2 3 5 7 11 13 17 19 23

  Arm logo
Important information

This site uses cookies to store information on your computer. By continuing to use our site, you consent to our cookies.

Change Settings

Privacy Policy Update

Arm’s Privacy Policy has been updated. By continuing to use our site, you consent to Arm’s Privacy Policy. Please review our Privacy Policy to learn more about our collection, use and transfers
of your data.