How to optimize Sieve of Eratosthenes further

Question

I was solving Project Euler problem 10 and I was able to do so using the Sieve of Eratosthenes, but now I'd like to optimize the code a bit further.

Considering the fact that all prime numbers greater than 3 are of the form 6k+1 or 6k-1 I only set those values in the array as true, but not all numbers of that form will be prime, so I have to sieve through the values and remove the non primes, and my code is as follows:

public static bool[] GeneratePrimes(int bound)
    {
        bool[] isPrime = new bool[bound];
        isPrime[2] = true;
        isPrime[3] = true;

        // Taking into account that all primes greater than 2 and 3
        // Are of the form 6k+1 or 6k-1

        for (int k = 6; k < isPrime.Length; k += 6)
        {
            if (k + 1 < isPrime.Length) isPrime[k + 1] = true;
            isPrime[k - 1] = true;
        }

        // At this point we still have some numbers that aren't prime marked as prime
        // So we go over them with a sieve, also we can start at 3 for obvious reasons

        for (int i = 3; i * i <= bound; i += 2)
        {
            if (isPrime[i])
            {
                // Can this be optimized?
                for (int j = i; j * i <= bound; j++)
                    isPrime[i * j] = false;
            }
        }

        return isPrime;
    }
}

So how can I optimize the code that I sieve through less numbers? For example if my number is 5, numbers such as 10,15,20 are already stroked through, but 25 for example isn't so is it possible to only go through values such is 25?

Have all the numbers in your range in a list. Remove them from your list is you go through them. — Kent Kostelac
You can generalize to larger primetorials, e.g. all primes > 5 are of the form 30k+{1, 7, 11, 13, 17, 19, 23, 29}, all primes > 7 are of the form 210k + {1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209}. And so on. — President James K. Polk

user448810 user448810 · Accepted Answer · 2017-12-15T14:03:51

Paul Pritchard has done much work with wheel sieves that extend your 6k±1 idea to larger prime wheels. Google for "pritchard wheel sieve" or look at my blog to get started.

How to optimize Sieve of Eratosthenes further

2 Answers