patterncsharpModerate

Sieve31, my sieve of Eratosthenes returning IEnumerable<int>

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

eratosthenessievereturningsieve31intienumerable

Problem

This very fast, simple sieve quickly finds 31 bit primes. It uses a memory efficient BitArray for odd numbers.

How a 32 bit int is a 31 bit prime

Since a prime number must be > 1, the sign bit has no bearing, leaving 31 bits to store the positive numbers. This differs from uint which truly would be 32 bit primes.

See this Microsoft link on Magic Numbers.

If you find the value 2147483647 on that page you will see this text:

The maximum signed 32 bit value. Largest 31 bit prime.

On an unrelated note, the Magic Numbers link has some pretty interesting things in it.

public static class Sieve31 
{
    public static IEnumerable Primes(int upperLimit)
    {
        if (upperLimit  ToNumber = delegate(int index)  { return (2 * index) + offset; };
        Func ToIndex  = delegate(int number) { return (number - offset) / 2; };
        var bits = new BitArray(ToIndex(upperLimit) + 1, defaultValue: true);
        var upperSqrtIndex = ToIndex((int)Math.Sqrt(upperLimit));
        for (var i = 0; i  i) && (j < bits.Length); j += number)
            {
                bits[j] = false;
            }
        }
        // Output remaining primes once bit array is fully resolved:
        for (var i = upperSqrtIndex + 1; i < bits.Length; i++)
        {
            if (bits[i])
            {
                yield return ToNumber(i);
            }
        }
    }
}

Example Usage

Here’s a simple example that counts the number of primes found and finds the largest one.

var count = 0;
var largest = 0;
var primes = Sieve31.Primes(int.MaxValue);
foreach (var prime in primes)
{
    count++;
    largest = prime;
}

Worst Case Scenario: int.MaxValue

The BitArray will have a Length of 1,073,741,823 bits, which is 128 megabytes. This will yield 105,097,565 primes.

If you want to store the primes to a List, the code is quite easy:

var primeList = Sieve31.Primes(int.MaxValue).ToList();

The resulting list would require 409 megabytes, in addition

Solution

About the only huge, performance-impacting change I can see that would be necessary is replacing the BitArray for a literal bool array.

This actually has a huge speed impact.

So, making that change, and inverting the related conditions causes us to have the following method:

public static IEnumerable Primes(int upperLimit)
{
    if (upperLimit  ToNumber = delegate (int index) { return (2 * index) + offset; };
    Func ToIndex = delegate (int number) { return (number - offset) / 2; };
    var bits = new bool[ToIndex(upperLimit) + 1];
    var upperSqrtIndex = ToIndex((int)Math.Sqrt(upperLimit));
    for (var i = 0; i  i) && (j < bits.Length); j += number)
        {
            bits[j] = true;
        }
    }
    // Output remaining primes once bit array is fully resolved:
    for (var i = upperSqrtIndex + 1; i < bits.Length; i++)
    {
        if (!bits[i])
        {
            yield return ToNumber(i);
        }
    }
}

You'll notice that I inverted all the booleans on the bits value, to make sure that requiring a default of false instead of true now would not create issues.

As far as speed goes, the difference seems to be performing in 63.3% of the time of your original method. (For a limit of 100,000,000 the modified version I have here is about 2486ms, yours is about 3917ms.)

Other than that, there is really not much you can do about performance overall.

As far as readability, I would never one-line an if statement without braces.

I'm speaking about:

if (bits[i]) continue;

Break that down into two-lines, it won't hurt anything. ;)

if (bits[i])
    continue;

You could also do for a little whitespace to break logical portions of your algorithm out.

public static IEnumerable Primes(int upperLimit)
{
    if (upperLimit  ToNumber = delegate (int index) { return (2 * index) + offset; };
    Func ToIndex = delegate (int number) { return (number - offset) / 2; };

    var bits = new bool[ToIndex(upperLimit) + 1];
    var upperSqrtIndex = ToIndex((int)Math.Sqrt(upperLimit));

    for (var i = 0; i  i) && (j < bits.Length); j += number)
        {
            bits[j] = true;
        }
    }

    // Output remaining primes once bit array is fully resolved:
    for (var i = upperSqrtIndex + 1; i < bits.Length; i++)
    {
        if (!bits[i])
        {
            yield return ToNumber(i);
        }
    }
}

I know, old question, but I felt it deserved a little attention.

Code Snippets

public static IEnumerable<int> Primes(int upperLimit)
{
    if (upperLimit < 2)
    {
        throw new ArgumentException("Upper Limit be must greater than or equal to 2.");
    }
    yield return 2;
    if (upperLimit == 2)
    {
        yield break;
    }
    // Check odd numbers for primality
    const int offset = 3;
    Func<int, int> ToNumber = delegate (int index) { return (2 * index) + offset; };
    Func<int, int> ToIndex = delegate (int number) { return (number - offset) / 2; };
    var bits = new bool[ToIndex(upperLimit) + 1];
    var upperSqrtIndex = ToIndex((int)Math.Sqrt(upperLimit));
    for (var i = 0; i <= upperSqrtIndex; i++)
    {
        // If this bit has already been turned off, then its associated number is composite. 
        if (bits[i]) continue;
        var number = ToNumber(i);
        // The instant we have a known prime, immediately yield its value.
        yield return number;
        // Any multiples of number are composite and their respective bits should be turned off.
        for (var j = ToIndex(number * number); (j > i) && (j < bits.Length); j += number)
        {
            bits[j] = true;
        }
    }
    // Output remaining primes once bit array is fully resolved:
    for (var i = upperSqrtIndex + 1; i < bits.Length; i++)
    {
        if (!bits[i])
        {
            yield return ToNumber(i);
        }
    }
}

if (bits[i]) continue;

if (bits[i])
    continue;

public static IEnumerable<int> Primes(int upperLimit)
{
    if (upperLimit < 2)
    {
        throw new ArgumentException("Upper Limit be must greater than or equal to 2.");
    }

    yield return 2;

    if (upperLimit == 2)
    {
        yield break;
    }

    // Check odd numbers for primality
    const int offset = 3;
    Func<int, int> ToNumber = delegate (int index) { return (2 * index) + offset; };
    Func<int, int> ToIndex = delegate (int number) { return (number - offset) / 2; };

    var bits = new bool[ToIndex(upperLimit) + 1];
    var upperSqrtIndex = ToIndex((int)Math.Sqrt(upperLimit));

    for (var i = 0; i <= upperSqrtIndex; i++)
    {
        // If this bit has already been turned off, then its associated number is composite. 
        if (bits[i])
            continue;

        // The instant we have a known prime, immediately yield its value.
        var number = ToNumber(i);
        yield return number;

        // Any multiples of number are composite and their respective bits should be turned off.
        for (var j = ToIndex(number * number); (j > i) && (j < bits.Length); j += number)
        {
            bits[j] = true;
        }
    }

    // Output remaining primes once bit array is fully resolved:
    for (var i = upperSqrtIndex + 1; i < bits.Length; i++)
    {
        if (!bits[i])
        {
            yield return ToNumber(i);
        }
    }
}

Context

StackExchange Code Review Q#92366, answer score: 14

Revisions (0)

No revisions yet.