Dictionary of Primes

Question

I was trying to create this helper function in C# that returns the first n prime numbers. I decided to store the numbers in a dictionary in the <int,bool> format. The key is the number in question and the bool represents whether the int is a prime or not. There are a ton of resources out there calculating/generating the prime numbers(SO included), so I thought of joining the masses by crafting another trivial prime number generator.

My logic goes as follows:

public static Dictionary<int,bool> GetAllPrimes(int number)
    {
        Dictionary<int, bool> numberArray = new Dictionary<int, bool>();


        int current = 2;
        while (current <= number)
        {
            //If current has not been marked as prime in previous iterations,mark it as prime
            if (!numberArray.ContainsKey(current))
                numberArray.Add(current, true);

            int i = 2;
            while (current * i <= number)
            {
                if (!numberArray.ContainsKey(current * i))
                    numberArray.Add(current * i, false);
                else if (numberArray[current * i])//current*i cannot be a prime
                    numberArray[current * i] = false;
                i++;

            }
            current++;
        }
        return numberArray;
    }

It will be great if the wise provide me with suggestions,optimizations, with possible refactorings. I was also wondering if the inclusion of the Dictionary helps with the run-time of this snippet.

Answer 1

The first thing that bothers is that, why are you storing the number itself ?

Can't you just use the index itself which will represent the number?

PS: I'm not a c# developer so maybe it is not possible with a dictionary, but it can be done with the appropriate structure.

Answer 2

First, you only have to loop untill the square root of the number. Make all numbers false by default and have a simple flag that you set true at the beginning of every iteration.

Further, don't store it in a dictionary. Make it a bool array and have the index be the number you're looking for. Only 0 won't make any sense, but that doesn't matter. You don't have to init either; bools are false by default. Just declare an bool[] of number length.

Then, I would init like this:

primes[2] = true;
for(int i = 3; i < sqrtNumber; i += 2) {

}

So you skip all the even numbers automatically.

By the way, never declare a variable (i) in a loop, it makes it slower.

So that's about it. For more info see this page.

Answer 3

Storing integers explicitly needs at least 32 bits per prime number, with some overhead for the container structure.

At around 2³¹, the maximal value a signed 32 bit integer can take, about every 21.5th number is prime. Smaller primes are more dense, about 1 in ln(n) numbers is prime around n.

This means it is more memory efficient to use an array of bits than to store numbers explicitly. It will also be much faster to look up if a number is prime, and reasonably fast to iterate through the primes.

It seems this is called a BitArray in C# (in Java it is BitSet).

Answer 4

I'm pretty sure the Dictionary actually hurts performance, since it doesn't enable you to perform the trial divisions in an optimal order. Traditionally, you would store the known primes so that they could be iterated from smallest to largest, since smaller primes are factors of more composite numbers than larger primes. Additionally, you never need to try division with any prime larger than the square root of the candidate prime.

Many other optimizations are possible (as you yourself point out, this problem has been studied to death) but those are the ones that I can see off the top of my head.

Answer 5

1) From the perspective of the client to this function, wouldn't it be better if the return type was bool[] (from 0 to number perhaps)? Internally, you have three states (KnownPrime, KnownComposite, Unknown), which could be represented by an enumeration. Storing an an array of this enumeration internally, prepopulated with Unknown, will be faster than a dictionary.

2) If you stick with the dictionary, the part of the sieve that marks multiples of the current number as composite could be replaced with a numberArray.TryGetValue() pattern rather than multiple checks for ContainsKey and subsequent retrieval of the value by key.

Answer 6

The dictionary really doesn't make sense here -- just store all primes up to a given number in a list. Then follow these steps:

Is given number in the list?  
    Yes - it's prime.  Done.
Not in list
Is given number larger than the list maximum?
    No - it's not prime.  Done.
Bigger than maximum; need to fill list up to maximum.
Run a sieve up to given number.
Repeat.

Answer 7

The trouble with returning an object that holds the primes is that unless you're careful to make it immutable, client code is free to mess up the values, in turn meaning you're not able to cache the primes you've already calculated.

How about having a method such as:

bool IsPrime(int primeTest);

in your helper class that can hide the primes it's already calculated, meaning you don't have to re-calculate them every time.