Tag Archives: Primes

The Sieve of Atkin in C#

I have previously written about the Sieve of Eratosthenes, which is an algorithm for finding primes. This algorithm worked very well for most of the prime related Euler Problems. However, for one of them it just didn’t do it. Well, it did it, but it did it kind of slow. The problem was to calculate the sum of all the primes below two million, and with that algorithm this took close to 2 seconds on my machine. Not too long you might think, but compared to my other solutions it is ages and ages. So I started to see if I could find a more efficient algorithm to use for that problem.

I quickly found one called the Sieve of Atkin. The Atkin algorithm works similarly to the original Eratosthenes one, but has a more fancy way of sieving out numbers which means it can work a lot faster. However, this also means that it needs to work towards an upper limit and that it have to find all the primes up to that limit in advance. In other words it cannot work incrementally and lazily like my Eratosthenes implementation.

Continue reading The Sieve of Atkin in C#

The Sieve of Eratosthenes in C#

In some of the Project Euler problems we have needed a source of primes. One algorithm for finding primes is called the Sieve of Eratosthenes. This algorithm is both pretty simple to understand and to implement. It is also fairly fast and usable, at least for the lower primes.

My implementation is based upon the algorithm described on the Wikipedia page and some helpful optimizations I found in an article at Black Wasp. The differences from the original algorithm and the solution at Black Wasp is that it finds the primes incrementally and that it only looks for a new prime when asked.

Continue reading The Sieve of Eratosthenes in C#