C#: Implementation of the Sieve of Atkin

Question

I was wondering if someone here have a good implementation of the Sieve of Atkin that they would like to share. I am trying to implement it, but can't quite wrap my head around it. Here is what I have so far. ``` public class Atkin : IEnumerable { private readonly List primes; private readonly ulong limit; public Atkin(ulong limit) { this.limit = limit; primes = new List(); } private void FindPrimes() { var isPrime = new bool[limit + 1]; var sqrt = Math.Sqrt(limit); for (ulong x = 1; x <= sqrt; x++) for (ulong y = 1; y <= sqrt; y++) { var n = 4*x*x + y*y; if (n <= limit && (n % 12 == 1 || n % 12 == 5)) isPrime[n] ^= true; n = 3*x*x + y*y; if (n <= limit && n % 12 == 7) isPrime[n] ^= true; n = 3*x*x - y*y; if (x > y && n <= limit && n % 12 == 11) isPrime[n] ^= true; } for (ulong n = 5; n <= sqrt; n++) if (isPrime[n]) for (ulong k = n*n; k <= limit; k *= k) isPrime[k] = false; primes.Add(2); primes.Add(3); for (ulong n = 5; n <= limit; n++) if (isPrime[n]) primes.Ad…

Accepted Answer

This code:

```
for (ulong k = n*n; k <= limit; k *= k)
  isPrime[k] = false;
```

doesn't seem to be a faithful translation of this pseudocode:

```
is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit}
```

Your code looks like it will run for n * n, n ^ 4, n ^ 8, etc. i.e. squaring each time instead of adding n-squared each time. Try this:

```
ulong nSquared = n * n;
for (ulong k = nSquared; k <= limit; k += nSquared)
  isPrime[k] = false;
```

C#: Implementation of the Sieve of Atkin

Solution

Problem

Related problems