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
