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 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 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);
myBA1.SetAll(true);
myBA1[0] = myBA1[1] = false;
int thisFactor = 2;
int lastSquare = 0;
int thisSquare = 0;
while (thisFactor * thisFactor <= topCandidate)
{
int mark = thisFactor + thisFactor;
while (mark <= topCandidate)
{
myBA1[mark] = false;
mark += thisFactor;
}
thisSquare = thisFactor * thisFactor;
for (; lastSquare < thisSquare; lastSquare++)
{
if (myBA1[lastSquare]) totalCount++;
}
thisFactor++;
while (!myBA1[thisFactor]) { thisFactor++; }
}
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 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.
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.
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);
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.