Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

Archive for October 4th, 2006

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

Posted by tekpool on October 4, 2006

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

Advertisements

Posted in Algorithms, C++, General, Microsoft, Number Theory, Progamming Languages | Leave a Comment »

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

Posted by tekpool on October 4, 2006

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

Posted in Algorithms, C++, General, Microsoft, Number Theory, Progamming Languages | Leave a Comment »