O'Reilly logo

Haskell Cookbook by Yogesh Sajanikar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Implementing Eratosthenes Sieve

In this recipe, we will look at a prime number calculator called Eratosthenes Sieve. It is an old algorithm for finding prime numbers. The prime numbers are found by crossing out composite numbers. The sieve works as follows: 

  1. Start with 2, a known prime. Strike out all the numbers that are multiples of 2.
  2. Start with the next unmarked number, which will be the next prime (since it is not divided by any prime before). Repeat the procedure of marking all the multiples.
  3. Repeat the procedure.

For more information, visit https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required