News & Articles:

Kata: Sieving for Primes

The Sieve of Eratothenes is an ancient way of determining Prime Numbers. It also makes for an interesting coding exercise. (I was once set it in a programming exam. I did badly.)

Background

A Prime Number is any positive integer greater than one that has no positive divisors other than one and itself. A number that is not prime is called a Composite Number.

The sieve starts with a list of all possible numbers up to some limit. The first stage is to remove all numbers that are divisible by two. Once this is done, the process is repeated for the highest number not already removed (the first time it will be three), and so on. Once all possible numbers have been tried, the numbers that remain are prime numbers. (It is important to understand how the sieve works before starting to code; it might be useful to try it with pen and paper on numbers up to 100).

Task

Write a program to determine all the prime numbers up to some given limit. The limit can come from the command line or can be entered by the user in response to a prompt. Use the sieve method described above.

Note that several optimisations are possible. For example, if you try the exercise by hand you will notice that you cross off very few numbers when using the factor 11. Why is this? (They have all already been crossed out by lower factors.) Other improvements on the outline above are possible.

Creative Commons Licence
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Posted in Technical

Tags: , ,