Programming Challenge 20 - Sieve of Erathostenes

A prime number is any integer (except 1) that can only be divided by itself or 1 without a remainder. The first ten prime numbers are thus 2,3,5,7,11,13,17,19,23,29. Apart from 2, prime numbers have be odd as all even numbers can be divided by 2.

Prime Numbers are very useful in encryption and hashing and being able to determine if ant given integer is prime is handy.

Rather than have you devise you own method which would be a major reinvention of the wheel, there is an algorithm called the Sieve of Eratosthenes.

That wikipedia link describes the sieve like this.

Sift the Two's and sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Basically you start with a set of 5 million numbers, then you remove all the numbers (except 2) that divide by 2 then those that divide by (except 3) then 5 and so on. After you've done those, what's left is prime.

The Competition

Implement the sieve to work out the primes up to 5 million as quick as possible. Output 5 prime numbers at these positions.

129
817
2679
34,612
125,897

Ie just as 29 is prime number 10, what is the 129th prime number? If there aren't 125,897 primes before you get to 5 million then the first four numbers will do.

Oh and total up the first 10,000 primes and output that number as well.

Please include the total time it took. This is the code that you can use for timing.

• How To Time C Code.
• How To Time C++ Code.
• How To Time C# Code.

Results

Congratulations to Zufolek whose program in C came first but only milliseconds ahead of 2nd and 3rd places. Thanks to all 19 entrants with entries from Lebanon to New Zealand and places in between. Including from two teenagers.

1. Zufolek (USA,29) - C Time = 0.011825
2. Joshua Warner (USA) - C++ Time = 0.0128258
3. Matt Osborn (New Zealand) - C++ Time = 0.0216859
4. Sanko(Belarus) - C++ Time = 0.0304544
5. Nick Bellow (USA,22) - C++ Time = 0.0327026
6. Peter Jansson (Sweden,37) Peter's Blog - C++ Time = 0.0361838
7. st0le(India) - C++ Time = 0.0383
8. Clinton Shepherd (USA) - C# Time = 0.11929
9. John Granström (Sweden,17) - C# Time = 0.11966
10. Scott Frick (USA,40) - C Time = 0.157984
11. Klins (India,20) - C++ Time = 0.264901
12. Jonathon Hamrick (USA) - C++ Time = 0.28536
13. Sumit Kakar (USA) - C# Time = 0.2928775
14. Vivek T S (India) - C++ Time = 0.479495
15. Chris Greth - C++ Time = 2.15333
16. Chetan Kakkar (India,15) - C Time = 2.328
17. Navaneetha Krishnan (India,25) - C# Time = 9.203

Two got the answer wrong.

Wrong Answers

1. Mohamad Alwani(Lebanon,24) - C# Time = 0.0304544
2. Chris Wallis(UK) - C# Time = 0.27065

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Challenge 20 email address with the subject line Programming Challenge 20.

It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is January 31 2009.

The top ten entries will be listed, judged purely by myself. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

Have fun!

More Programming Challenges

• Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
• Link to Programming Challenge 2 - Count the Islands. (Finished)
• Link to Programming Challenge 3 - Manage Elevators. (Finished)
• Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
• Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
• Link to Programming Challenge 8 - Score Poker Hands - (Finished)
• Link to Programming Challenge 9 - Manage a Data structure - (Finished)
• Link to Programming Challenge 10 - Hide Text (Finished)
• Link to Programming Challenge 11 - Match Sets of Cards (Finished)
• Link to Programming Challenge 12 - Calculate Shortest Path - Completed)
• Link to Programming Challenge 13 - Play Battleships (Finished)
• Link to Programming Challenge 14 - Multiply Large Numbers(Completed)
• Link to Programming Challenge 15 - Generate a Dungeon (Completed)
• Link to Programming Challenge 16 - Solve 1,000 Sliding Puzzles ( Completed)
• Link to Programming Challenge 17 - Implement Life (Completed)
• Link to Programming Challenge 19 - Complete a Puzzle (Deadline Dec 31 2008)