15,922,155 members
Articles / Desktop Programming / Win32

# Eratosthenes/Sundaram/Atkins Sieve Implementation in C#

Rate me:
8 Nov 2012CPOL4 min read 48.3K   769   24   12
C# Implementation of Eratosthenes/Sundarm/Atkins Sieve to generate prime numbers and comparison of performance numbers between the three implementations.

## 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.

C#
```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;
}

#### 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.

C#
```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.

C#
```/* 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

C#
```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.

Written By
United States
Ashraff is working as software engineer and develops financial applications.His programming experience includes C / C++ /, C#/.NET, Java, JavaScript, HTML, Flex, PHP, PERL.His interests are Secuirty, Mobile Development, Algorithms and Data Structures and AI.

## Comments and Discussions

 First Prev Next
 There is a flaw in your code. yrimal1-Feb-19 2:41 yrimal 1-Feb-19 2:41
 Java program that implements the Sieve OF ERATOSTHENES to find the prime numbers Member 870389717-Apr-13 6:27 Member 8703897 17-Apr-13 6:27
 My vote of 5 Ahmed Ibrahim Assaf5-Dec-12 23:24 Ahmed Ibrahim Assaf 5-Dec-12 23:24
 Optimised Sieve Of Eratosthenes Member 205300612-Nov-12 2:04 Member 2053006 12-Nov-12 2:04
 Re: Optimised Sieve Of Eratosthenes Ashraff Ali Wahab12-Nov-12 4:45 Ashraff Ali Wahab 12-Nov-12 4:45
 Great article Marc Clifton8-Nov-12 4:44 Marc Clifton 8-Nov-12 4:44
 Re: Great article Ashraff Ali Wahab8-Nov-12 5:11 Ashraff Ali Wahab 8-Nov-12 5:11
 Re: Great article Marc Clifton8-Nov-12 6:16 Marc Clifton 8-Nov-12 6:16
 Re: Great article Ashraff Ali Wahab8-Nov-12 6:34 Ashraff Ali Wahab 8-Nov-12 6:34
 Another primes generator algorithm ? Perić Željko8-Nov-12 2:02 Perić Željko 8-Nov-12 2:02
 Re: Another primes generator algorithm ? Ashraff Ali Wahab8-Nov-12 3:33 Ashraff Ali Wahab 8-Nov-12 3:33
 Re: Another primes generator algorithm ? Perić Željko8-Nov-12 7:34 Perić Željko 8-Nov-12 7:34
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jun-24 22:43 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.