4
\$\begingroup\$

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 < 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 < 0 || number > 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 < 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 <= highestNumber && j > 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(string.Join(", ", Enumerable.Range(0, 100).Where(sieve.IsPrime)));
        Console.WriteLine("Took {0}ms", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }        
}

Result of simple test harness

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?

\$\endgroup\$
  • 3
    \$\begingroup\$ Why not use the BitArray class for bits packing? \$\endgroup\$ – Dmitry Oct 10 '16 at 15:52
  • \$\begingroup\$ @Dmitry ignorance :) Thanks - that does seem like the perfect data structure for this. \$\endgroup\$ – RobH Oct 10 '16 at 16:10
3
\$\begingroup\$

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 < 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 < 0 || number > 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 < 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 < highestNumber && j > 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<long> 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 < max && j > 0; j += n)
          {
            bits[(int)j] = true;
          }
        }
      }
    }

    IEnumerable<long> 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It's definitely a simpler implementation! I knew about the BitArray class but hadn't ever found a place where it made sense to use it. Now I'll know when it's a good thing to use. \$\endgroup\$ – RobH Oct 11 '16 at 7:31
  • \$\begingroup\$ You could post this as a question as there are a few stylistic issues. E.g. EnumUnevens is a bad name for method. \$\endgroup\$ – RobH Oct 11 '16 at 8:02
  • \$\begingroup\$ @RobH: 'Uneven' is a bad direct translation from my native language, but I've changed it to EnumOddNumbers instead :-). Anyway I'll leave it as an answer. \$\endgroup\$ – Henrik Hansen Oct 11 '16 at 8:46
2
\$\begingroup\$
private void Populate()
{
    for (var i = 2; i < 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 <= highestNumber && j > 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.
}  
  • It's always only guessing wether the compiler will optimize some conditions, so I would like to suggest to pre calculate Math.Sqrt(highestNumber) and store it in a variable to use in the for condition of the outer loop.

- Because i is always >0 (you are starting at 2) the j > 0 condition of the inner loop can be removed.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ The j > 0 check is because j can overflow (+= i) and wrap round to being negative. \$\endgroup\$ – RobH Oct 10 '16 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.