a superfast way to search for prime numbers [sieve of eratosthenes]

Tags: ProjectEuler, csharp, math, SieveofEratosthenes

I've been dabbling a little lately on pure computer science stuff like computational complexity, algorithm design and math. (And interestingly I failed high school math quite badly once)

Project Euler has been an interesting learning/practice ground : http://projecteuler.net/about

The problems here involve some math, but also deal with time complexity. If done wrong, some of the solutions to their problems could take days or longer (maybe years) to complete.

Today at problem 10 this was the case:

Find the sum of all the primes below two million.

A normal brute-force method just took way too long. On a relatively fast machine using the following method for checking for primes took nearly 22 minutes to run:

Enter- Sieve of Eratosthenes : An interestingly fast way to find primes.

You make a list of all your target numbers, in our case 1 to 2 million, then remove (or filter) all the multiples of numbers starting with two. You keep going removing multiples and your list ends up being only prime numbers.

Here's a visualization from the wikipedia article:

Visualization of Sieve of Eratosthenes

Here is a snippet of how I implemented it for the problem. See my whole problem solved here

Drum roll! It took ~80 millisconds to run!

I'm aching to sneak in the time to get to Level 1 which is 25 problems solved! I just got my decathlete badge today. Unfortunately the badges don't show in the little flair, they only show in your statistics page:

Project Euler Badge

I'm put up all my problems as I go on github. Check it out here:

Hopefully this was somewhat insightful.

Comments powered by Disqus