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\$
2
  • 3
    \$\begingroup\$ Why not use the BitArray class for bits packing? \$\endgroup\$
    – Dmitry
    Commented Oct 10, 2016 at 15:52
  • \$\begingroup\$ @Dmitry ignorance :) Thanks - that does seem like the perfect data structure for this. \$\endgroup\$
    – RobH
    Commented Oct 10, 2016 at 16:10

2 Answers 2

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.

\$\endgroup\$
3
  • \$\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
    Commented Oct 11, 2016 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
    Commented Oct 11, 2016 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\$
    – user73941
    Commented Oct 11, 2016 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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