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 =&gt; 1, 4, 6 and 8 have been marked non-prime.
    private readonly byte[] data;

    private SieveOfEratosthenes(int highestNumber)
    {
        if (highestNumber &lt; 1)
        {
            throw new ArgumentOutOfRangeException(nameof(highestNumber));
        }
        this.highestNumber = highestNumber;
        var sizeRequired = (int)Math.Ceiling(highestNumber/8.0);
        data = new byte[sizeRequired];
    }

    public static SieveOfEratosthenes CreateSeive(int highestNumber)
    {
        var result = new SieveOfEratosthenes(highestNumber);
        result.Populate();
        return result;
    }

    public bool IsPrime(int number)
    {
        if (number &lt; 0 || number &gt; 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] &gt;&gt; (number-1)%8) &amp; 1) == 0;
    }

    private void Populate()
    {
        for (var i = 2; i &lt; Math.Sqrt(highestNumber); i++)
        {
            if (!IsPrime(i))
            {
                continue;
            }
            // j += i can overflow so need to guard against that in for loop.
            for (var j = i * i; j &lt;= highestNumber &amp;&amp; j &gt; 0; j += i)
            {
                data[(j-1) / 8] = (byte)(data[(j-1) / 8] | (1 &lt;&lt; ((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(string.Join(", ", Enumerable.Range(0, 100).Where(sieve.IsPrime)));
        Console.WriteLine("Took {0}ms", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }        
}




On my machine it takes about 20 seconds to seive to int.MaxValue which takes just over 250mb of memory (roughly int.MaxValue/8 bytes).

Any room for improvement, bugs or style issues?
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 &lt; 1)
          {
            throw new ArgumentOutOfRangeException(nameof(highestNumber));
          }
          this.highestNumber = highestNumber;
          data = new BitArray(highestNumber);
        }

        public static SieveOfEratosthenes CreateSeive(int highestNumber)
        {
          var result = new SieveOfEratosthenes(highestNumber);
          result.Populate();
          return result;
        }

        public bool IsPrime(int number)
        {
          if (number &lt; 0 || number &gt; 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 &lt; sqrt; i++)
          {
            if (data[i]) // not a prime
            {
              continue;
            }
            // j += i can overflow so need to guard against that in for loop.
            for (var j = i * i; j &lt; highestNumber &amp;&amp; j &gt; 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&lt;long&gt; 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 &lt; max &amp;&amp; j &gt; 0; j += n)
          {
            bits[(int)j] = true;
          }
        }
      }
    }

    IEnumerable&lt;long&gt; EnumOddNumbers(long max)
    {
      for (long i = 1; i &lt; 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 &lt; 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.