Finding and testing primality

Question

I have written a class who is responsible for both enumerating primes and testing the primality of a number.

Here is the code :

public static class Primes
{
    private static ulong g_MaxTested;
    private static ulong g_MaxFound;

    private static readonly HashSet<ulong> g_KnownPrimes;

    static Primes()
    {
        // All primes below 1000 (http://en.wikipedia.org/wiki/Primes)
        g_KnownPrimes = new HashSet<ulong>() {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 
            79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 
            167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 
            257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
            353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 
            449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 
            563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 
            653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 
            761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
            877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 
            991, 997
        };

        g_MaxTested = 997;
        g_MaxFound = 997;

    }

    private static void EnsureExploredUpTo(ulong upperBound)
    {
        if (upperBound <= g_MaxTested) return;

        for (g_MaxTested += 2; g_MaxTested <= upperBound; g_MaxTested += 2)
        {
            if (TestPrimality(g_MaxTested))
            {
                g_KnownPrimes.Add(g_MaxTested);
                g_MaxFound = g_MaxTested;
            }
        }
    }

    private static bool TestPrimality(ulong value)
    {
        if (value == 1) return false;
        var sqrt = (ulong)Math.Sqrt(value);
        return !g_KnownPrimes
            .TakeWhile(x => x <= sqrt)
            .Any(x => value % x == 0);
    }

    public static bool IsPrime(ulong value)
    {
        if (value == 1) return false;
        EnsureExploredUpTo(value);
        return g_KnownPrimes.Contains(value);
    }

    public static IEnumerable<ulong> GetPrimes(ulong upperBound = ulong.MaxValue)
    {
        // First return all known primes : 
        foreach (var prime in g_KnownPrimes)
        {
            if (prime > upperBound) yield break;
            yield return prime;
        }
        // then, if required, continue exploring :
        for (g_MaxTested += 2; g_MaxTested <= upperBound; g_MaxTested += 2)
        {
            if (TestPrimality(g_MaxTested))
            {
                g_KnownPrimes.Add(g_MaxTested);
                g_MaxFound = g_MaxTested;
                yield return g_MaxTested; // yield the result for immediate use
            }
        }
    }
}

Key concepts :

• The idea of the class is to maintain a "cursor" of explored number, and a list of known primes.
• The known primes (g_KnownPrimes) allows me to test a number like using a sieve (as a non prime number is always a multiple of another prime (TestPrimality method).
• When I want to test a number outside the explored number range, I explorer from the last tested to the number to test (EnsureExploreredUpTo method)
• When I want to enumerate all primes, I start to yield known primes, then use the same logic than EnsureExplorerdUpTo, but with yielding each prime found.

I have validated my code using these tests :

    [TestMethod()]
    public void GetPrimesTest()
    {
        var primes = Primes.GetPrimes();
        var enumerator = primes.GetEnumerator();

        Assert.IsTrue(enumerator.MoveNext());
        Assert.AreEqual(enumerator.Current, 2UL);
        Assert.IsTrue(enumerator.MoveNext());
        Assert.AreEqual(enumerator.Current, 3UL);

        do
        {
            Assert.IsTrue(enumerator.MoveNext());

        } while (enumerator.Current < 997); // Last prime below 1000

        Assert.IsTrue(enumerator.MoveNext());
        Assert.AreEqual(enumerator.Current, 1009UL);
        Assert.IsTrue(enumerator.MoveNext());
        Assert.AreEqual(enumerator.Current, 1013UL);
    }

    [TestMethod()]
    public void _1IsNotPrimeTest()
    {
        Assert.IsFalse(Primes.IsPrime(1));
    }
    [TestMethod()]
    public void _2IsPrimeTest()
    {
        Assert.IsTrue(Primes.IsPrime(2));
    }
    [TestMethod()]
    public void _3IsPrimeTest()
    {
        Assert.IsTrue(Primes.IsPrime(3));
    }
    [TestMethod()]
    public void _42IsNotPrimeTest()
    {
        Assert.IsFalse(Primes.IsPrime(42));
    }
    [TestMethod()]
    public void _2001IsNotPrimeTest()
    {
        Assert.IsFalse(Primes.IsPrime(2001));
    }

So my question are :

• Is this approach valid ? I've googled a bit but without finding better algorithms.
• I use the HashSet<ulong> class, as it seems to be the more efficient list for my case. Am I right ?
• I know this class is not thread safe at all. Can I "simply" make it thread-safe ? (maybe this should be a dedicated question on [so].

Answer 1

This is a valid sieve but the HashSet MAY not be as fast as an Array or ArrayList. These will preserve the order of the elements, so you could implement a quick membership check with a binary search. They would likely be faster to iterate over in general -- they should especially speed up iteration for testing the primality of a sequence of odd numbers. In 33% of the cases, the testing would not get past x % 3. Doing these tests in HashSet order wastes lots of time checking against higher primes in the HashSet that rarely change the outcome. Listing primes in a HashSet order that may change as the set of primes grows seems slightly less useful than listing in increasing order.

BTW, testing odd numbers for x % 2 is a waste of time, especially if that's going to be the first test -- you might want to consider pulling 2 out of your primes list and handling it separately only when you have to.

But you should definitely benchmark either of these suggestions on a mix of input sequences with typical numbers of input values, maximum input values, and tendencies to raise the high water value early vs. late in the sequence.

One last note: g_MaxFound doesn't cost much and is nice for diagnostic purposes, but it's not actually used in the implementation. I usually mark non-critical variables like this with special names or at least comments to avoid confusion with the operational values.

Answer 2

How large are the numbers that you will be testing for primality? If you have an upper bound then it might be better to use a sieve of Eratosthenes to find all the primes up to sqrt(upperBound). That way you don't need to keep checking whether you need to extend your explored range.

In answer to your questions:

1) Your approach seems valid. However, it might pay off to extend your explored range by more than 2 at a time using a sieve approach, e.g. start off with 1000 primes and then if you need more explore up to 10,000, then 100,000. Sieve's are quick and you'll avoid division.

2) A hash set seems reasonable. Another viable approach (for small g_MaxTested) is a BitArray. This becomes less appealing as g_MaxTested gets larger because the primes become more spread out.

3) A simple approach is to make each public method lock a locker object. This means only one thread can interact with your class at once.

If you want me to write some code to explain my points let me know.

Update

How about initialising the class with all the primes less than 10^7 (664,579 according to wikipedia), then if you get a number:

• < 10^7 do a simple membership check
• between 10^7 and (10^7)^2 see if any of your primes divide into it
• > 10^14 check whether any of your primes divide into it, if not see if any of the odd numbers in the range 10^7 to sqrt(number) divide it.

It is probably best to store the primes as uint rather than ulong to save on memory.

Also 10^7 is arbitrary and you should change this to suit your space / time requirements.

Answer 3

Some notes about the tests:

1. The first the method has a smell: Conditional Test Logic. I'd extract out the do-while loop to an enumeratePrimesBelow(ulong upperLimit) method. It would improve readability a lot.

2. Assert.IsFalse(Primes.IsPrime(1));
   

   I'd create a custom assertion method for that:

   public void AssertIsNotPrime(ulong value) {
       Assert.IsFalse(Primes.IsPrime(value));
   }
   

   It would make the tests easier to read.

3. _1IsNotPrimeTest, _2IsPrimeTest, _3IsPrimeTest, _42IsNotPrimeTest etc. should be a parameterized test. I don't know whether C# unit testing frameworks supports it or not.