Sieving for prime numbers
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.