Sieving for prime numbers

I wanted to implement the Sieve of Erathosthenes up to int.MaxValue in C#. No object is allowed to exceed 2Gb so you can't allocate a bool[int.MaxValue] array. In order to solve the problem, I created a class that packs the bits into an array of bytes instead.

I know that it's possible to use a segmented sieve: this was just for 'fun'.

public class SieveOfEratosthenes
{
    private readonly int highestNumber;

    // Flags for each number are stored packed in a byte array. 
    // Least significant bit is flag for 1 - by starting at 1 and not 0 we can seive to int.MaxValue
    //                             8 7 6 5 4 3 2 1
    // e.g. for highestNumber = 8: 1 0 1 0 1 0 0 1 => 1, 4, 6 and 8 have been marked non-prime.
    private readonly byte[] data;

    private SieveOfEratosthenes(int highestNumber)
    {
        if (highestNumber  highestNumber)
        {
            throw new ArgumentOutOfRangeException(nameof(number));
        }
        // 0 not stored in byte array so we have to test separately.
        if (number == 0)
        {
            return false;
        }
        return ((data[(number-1)/8] >> (number-1)%8) & 1) == 0;
    }

    private void Populate()
    {
        for (var i = 2; i  0; j += i)
            {
                data[(j-1) / 8] = (byte)(data[(j-1) / 8] | (1 << ((j-1) % 8)));
            }
        }
        data[0] = (byte)(data[0] | 1); // Mark 1 as not prime.
    }
}

The algorithm for the Populate method is just from the wikipedia article with true and false the other way around, see: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode

The reason I'm using a static factory method is that I don't like constructors that do non-trivial work.

Here's a simple test harness that prints the primes under 100:

```
class Program
{
static void Main(string[] args)
{
var sw = Stopwatch.StartNew();
var sieve = SieveOfEratosthenes.CreateSeive(100);
sw.Stop();
Console.WriteLine(s

For some kind of fun I've replaced your byte array with the buildin BitArray (as mentioned by Dmitry) in you class just to see the effect (it seems to be slightly faster). Further I've tried to implement the sieve algorithm as linq based. It all goes like this:

using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;

    namespace PrimesAndSieve
    {
      public class SieveOfEratosthenes
      {
        private readonly int highestNumber;

        private readonly BitArray data;

        private SieveOfEratosthenes(int highestNumber)
        {
          if (highestNumber  highestNumber)
          {
            throw new ArgumentOutOfRangeException(nameof(number));
          }
          // 0 not stored in byte array so we have to test separately.
          //if (number == 0) ... as noted by Heslacher
          //{
          //  return false;
          //}
          return !data[number];
        }

        private void Populate()
        {
          var sqrt = Math.Sqrt(highestNumber);

          for (var i = 2; i  0; j += i)
            {
              data[j] = true;
            }
          }
          data[0] = true; // Mark 0 as not prime.
          data[1] = true; // Mark 1 as not prime.
        }
      }

  class PrimesBySieveAndLinq
  {
    public IEnumerable GetPrimes(long max)
    {
      yield return 2;

      BitArray bits = new BitArray((int)max);

      foreach (var n in EnumOddNumbers(max).Skip(1))
      {
        if (!bits[(int)n])
        {
          yield return n;
          for (long j = n * n; j  0; j += n)
          {
            bits[(int)j] = true;
          }
        }
      }
    }

    IEnumerable EnumOddNumbers(long max)
    {
      for (long i = 1; i < max; i += 2)
      {
        yield return i;
      }
    }
  }

      class Program
      {
        static void Main(string[] args)
        {
          int max = 10000; // 000000; // int.MaxValue;
          var sw = Stopwatch.StartNew();
          var sieve = SieveOfEratosthenes.CreateSeive(max);

          for (int i = 1; i < max; i++)
          {
            if (sieve.IsPrime(i))
            {
              Console.WriteLine(i);
            }
          }
          sw.Stop();
          var firstDuration = sw.ElapsedMilliseconds;

          Console.ReadLine();

          sw = Stopwatch.StartNew();
          PrimesBySieveAndLinq pbsl = new PrimesBySieveAndLinq();
          foreach (var prime in pbsl.GetPrimes(max))
          {
            Console.WriteLine(prime);
          }
          sw.Stop();
          Console.WriteLine();
          Console.WriteLine("Took {0}ms", firstDuration);
          Console.WriteLine($"Duration: {sw.ElapsedMilliseconds}");
          Console.WriteLine("END");
          Console.ReadLine();
        }
      }
    }

Note: If you try PrimesBySieveAndLinq.GetPrimes(int.MaxValue) it is very slow at the beginning, but speeds up after some 1000 of primes.

StackExchange Code Review Q#143806, answer score: 3