Prime Numbers: Finding the first N Primes – Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm

Q: Finding the first N Primes
Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm

We have been using regular Computer Science procedures for improving efficiency here. It’s time to borrow some good old Math theorms now. The first of the techniques, that I am going to use is the Sieve of Eratosthenes

This is an algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number you wish to include in the table. Cross out all numbers >2 which are divisible by 2 (every second number). Find the smallest remaining number >2 . It is 3. So cross out all numbers >3 which are divisible by 3 (every third number). Find the smallest remaining number >3 . It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number).

Continue until you have crossed out all numbers divisible by sqrt(n), The numbers remaining are prime.

This idea can be used easily to find all primes below a given number. But, how do you use this to find the first N primes. Here’s a quick idea, Use Erdos Prime Number Theorm. You use this to find a Cap, which is the number until which you need to check to get N primes.

float FindPrimeCap(int x) 
{ 
    float flX = (float) x; 
    float flCap = 1.0f; 
    for(float f=2.0f; flCap

FindPrimeCap uses Erdos Prime Number Theorm. Since this is asymptotic, it is not accurate enough for small numbers.
However, timing this code showed that this method was faster than all of the previous method we discussed.
In fact more prime were found in lesser time, using this method compared to the previous ones.

In a later post, We will analye the performance of all the methods we have discussed so far

Prime Numbers: Finding the first N Primes – Part 3 Prime Divisors

Q: Finding the first N Primes

In the last post we looked into making some improvements over Trivial Approaches

Lets look at ways into how we can make this faster. The improvements made in the last post where basically about skipping everyone second and third number, and not skipping divisors that are multiples of 2 and 3. This holds true, because, if the number were a multiple of 2 or 3, it would be dealt with in the first place, where we skipped all numbers that were multiples of 2’s and 3’s. Now this idea can be extended to number upto 5, 7, 11 and so one. The general way to do this will be to store the primes already found and only use these primes are divisors.

void GetPrimesPrimeDivisiors(int n) 
{ 
    int* prime = new int[n]; 
    prime[0]=2; 
    int count=1; 
    int j=3; 
    while(count

Prime Numbers: Finding the first N Primes – Part 2 Skipping Multiples

Q: Finding the first N primes.
In the last post, we looked into some trivial approaches. How can we make this faster?

Most of the work in problems like these (Finding matches) are spent in the core problem itself (Finding the match), in this case, Primality test. So lets look into how we can avoid this? One simple approach is to not do primality checks for even numbers

void GetPrimesSkipEven(int n) 
{ 
    // Start from 5 
    int j=3; 
    // Set count to 1 
    // 2 is already a prime 
    int count = 1; 
    while(count

Improvements In GetPrimesSkipEven:

1. Every second number (even) is not tested for primality
2. In primality test, division test are reduced by half, since we do not divide by even numbers any more (i+=2)
3. Modulo divisions are replaced by bit operators (i%2) == (i&1)

How can we get better,

void GetPrimesSkipSecondThird(int n) 
{ 
    // Start from 5 
    int j=5; 
    // Set count to 2, 
    // already 2 primes have been found (2 and 3) 
    int count = 2; 
    while(count

Improvements In GetPrimesSkipSecondThird:

1. Every second and third number is not tested for primality
2. In primality test, division test are reduced around 60%, since we do not divide by numbers divisible be 2 or 3
   Skip incrementing i by 2 or 4 (alternatively)
3. Modulo divisions are replaced by bit operators (i%2) == (i&1)

In a later post, we will look into the speeds of all these, but to those curious ones out there, I am list faster algorithms as we go by

Prime Numbers: Finding the first N Primes – Part 1 Trivial Approaches

Q: Finding whether or not a number is prime?

Sol: There are several ways to solve this problem. Lets look into some of the more trivial approaches as usual and try to improve on these as we move along.

By Definition, a prime number is a positive integer having exactly one positive divisor other than 1. Therefore the straightforward way to do this will be to check divisibility of the given number starting from 2 to the given number.

There are some easy ways to improve upon this basic approach.

1. You do not have to check for all numbers upto n. Some would argue that checking upto n/2 would suffice, since anything greater than this will not divide the given number as a whole number
2. Actually, you will not even need to go upto n/2. Checking upto sqrt(n) would suffice. This is because anything if there was a number greater than this that would actuall divide the divide the given number, you would have already visited the factor since that number will be less than or equal to sqrt(n). E.g If 91 was the given number, you would not have to check for numbers greater than 9. This is beacause although 13 divides 91, this would already have been found since you would have checked 7 prior to this and this is less that 9 (floor(sqrt(91))

void GetPrimes(int n) 
{ 
    // Start from 3 
    int j=3; 
    // There is already one prime (2), so set count=1 
    int count = 1; 
    while(count