Eratosthenes/Sundaram/Atkins Sieve Implementation in C#

• Download PrimeNumbers.zip - 17.5 KB

Introduction 

This article explains in detail about generating prime numbers using the four well known algorithm. This article doesn't talk about the algorithm itself but optimized implementation of the algorithm.

• Bruteforce method
• Sieve of Eratosthenes
• Sieve of Sundaram
• Sieve of Atkin

Background  

Prime numbers are the basis for the "Public Key Cryptography (PKC)". Instead of going too deep into PKC, let me give the how prime numbers are used. 

Let's take two prime number 7 and 13 and if I want to calculate the product, we can calculate it easily which is 91.Now,instead let's say I have number 91 and I want to find the pair of prime numbers whose product will give 91;It will be harder to find but we can find it eventually. If the number given is a 128 digit number ,then it is hard to find the factors quickly.

This "harder to factorize" prime number problem is used as a one-way function for the basis of PKC.

Using the code  

Brute Force Method  or Trial Division

Brute Force  method is the easiest method to find the prime number. In order to find whether a number is prime or not the number is divided by odd number and checked for remainder starting from 3 up to odd number whose square is less than the number we are checking.

If no remainder is available then the number is not prime otherwise it is. Below code snipped checks for it. The totalCount is initialized to 1 since 2 is prime number and ignored in our code.

int totalCount = 1;
bool isPrime = true;
for (long i = 3; i < topCandidate; i += 2)
{
    for (int j = 3; j * j <= i; j += 2)
    {
        if ((i % j) == 0) { isPrime = false; break; }
    }
    if (isPrime) { totalCount++; } else isPrime = true;
}
return totalCount; 

Sieve Of Eratosthenes 

Sieve of Eratosthenes is the ancient  algorithm to find the prime number and is the first efficient algorithm to be written.

The algorithm itself is quite simple. Let's say, in order to find prime number less than 10, a boolean array of length 10 is created which has values true for all. Starting from 2,the multiples of two are set to false in the array. This process is continues until the multiple of the number is less than 10.

Finally all the index of the boolean array which has value true is considered as Prime except index 1.

 Initial array                 : 1  1  1  1  1  1  1  1  1 1

1st Parse (2's multiple) :  1  1  1  0  1  0  1  0  1 0

2nd Parse (3's multiple) :  1  1  1  0  1  0  1  0  0 0

3rd Parse (4's multiple) :  1  1  1  0  1  0  1  0  0 0  

4th Parse (5's multiple) :  1  1  1  0  1  0  1  0  0 0 

5th parse is not possible since 6's multiple is greater than 10.The prime numbers are 2, 3, 5, and 7.

int totalCount = 0;
BitArray myBA1 = new BitArray(topCandidate + 1);

/* Set all but 0 and 1 to prime status */
myBA1.SetAll(true);
myBA1[0] = myBA1[1] = false;

/* Mark all the non-primes */
int thisFactor = 2;
int lastSquare = 0;
int thisSquare = 0;

while (thisFactor * thisFactor <= topCandidate)
{
    /* Mark the multiples of this factor */
    int mark = thisFactor + thisFactor;
    while (mark <= topCandidate)
    {
        myBA1[mark] = false;
        mark += thisFactor;

    }

    /* Print the proven primes so far */
    thisSquare = thisFactor * thisFactor;
    for (; lastSquare < thisSquare; lastSquare++)
    {
        if (myBA1[lastSquare]) totalCount++;

    }

    /* Set thisfactor to next prime */
    thisFactor++;
    while (!myBA1[thisFactor]) { thisFactor++; }

}
/* Print the remaining primes */
for (; lastSquare <= topCandidate; lastSquare++)
{
    if (myBA1[lastSquare]) { totalCount++; }

} 

This algorithm is efficient than our Brute force method but  is limited by memory constraint like any other prime number calculation algorithm.

Sieve of Sundaram

Sieve of Sundaram is efficient algorithm compared to Eratosthenes. It uses similar Sieve principle like Eratosthenes  but doesn't consider the even numbers.

It crosses out any number in the sieve (boolean array) which is of the form i+j+2ij and i+j+2ij<=n

where  n is the number which we want to find all the the prime numbers below.

           i >= 1 and less than < n/2

           j >= i and less than n

Finally the index in the sieve which has value true is multiplied by 2 and incremented by 1 to give the prime number. Below is the optimized implementation of the SOS.

/* SEIVE */
int maxVal = 0;
int denominator = 0;
for (int i = 1; i < k; i++)
{
    denominator = (i << 1) + 1;
    maxVal = (k - i) / denominator;
    for (int j = i; j <= maxVal; j++)
    {
        myBA1[i + j * denominator] = false;
    }
}
int prime= 0;
for (int i = 1; i < k; i++)
{
    if (myBA1[i])
    {
        totalCount++;
        prime= (i << 1) + 1; 
    }
}

The performance is better than Eratosthenes but suffers the half of the memory constrained suffered by  sieve of Eratosthenes.

Sieve of Atkin

Atkin's Sieve is improvement over Eratosthenes. Instead of looping through all the number to find out it is prime or not, it relies on quadratic equation and modulo 60 to find the patterns of prime/no prime and mark them in boolean array.

Below code implements Sieve of Atkin

int totalCount = 0;
BitArray isPrime = new BitArray(topCandidate + 1);
int squareRoot = (int)Math.Sqrt(topCandidate);
int xSquare = 1, xStepsize = 3;
int ySquare = 1, yStepsize = 3;
int computedVal = 0;

for (int x = 1; x <= squareRoot; x++)
{
    ySquare = 1;
    yStepsize = 3;
    for (int y = 1; y <= squareRoot; y++)
    {
        computedVal = (xSquare << 2) + ySquare;

        if ((computedVal <= topCandidate) && (computedVal % 12 == 1 || computedVal % 12 == 5))
            isPrime[computedVal] = !isPrime[computedVal];

        computedVal -= xSquare;
        if ((computedVal <= topCandidate) && (computedVal % 12 == 7))
            isPrime[computedVal] = !isPrime[computedVal];

        if (x > y)
        {
            computedVal -= ySquare << 1;
            if ((computedVal <= topCandidate) && (computedVal % 12 == 11))
                isPrime[computedVal] = !isPrime[computedVal];
        }
        ySquare += yStepsize;
        yStepsize += 2;
    }
    xSquare += xStepsize;
    xStepsize += 2;
}

for (int n = 5; n <= squareRoot; n++)
{
    if (isPrime[n] == true)
    {
        int k = n * n;
        for (int z = k; z <= topCandidate; z += k)
            isPrime[z] = false;
    }
}

for (int i = 1; i < topCandidate; i++)
{
    if (isPrime[i]) totalCount++;
}
return (totalCount + 2); // 2 and 3 will be missed in Sieve Of Atkins 

The above code is efficient than Eratosthenes  and inefficient or same as Sundaram in some cases. The reason being unnecessary computation performed for numbers which are not relevant. 

Lets say we need to find all the prime under 10. 4x^2+y^2 need to be performed for all the number less than square root of the 10 which is 3.  Operation 4 * (3^2) + 1 ^ 2 , 4 * (3^2) + 2 ^ 2 ,4 * (3^2) + 3 ^ 2  is unnecessary since the result is above 10.This cant be removed in a normal implementation. 

In the code attached a optimized implementation is provided which will ignore unnecessary calculation but also difficult to comprehend.

Points of Interest 

• More efficient implementation of all the algorithm.
• Overcoming memory constraint by using Paging, Clusters of machine and finding prime numbers quickly up to cryptographic standard.