TEKPOOL

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 < n)
	{
		// If its divisible by 2
		// its not a prime
		if(j&1==0) // if(j%2 ==0)
		{
			j++;
			continue;
		}

		int check = (int)sqrt(double(j));
		bool fPrimeFound=true;
		for(int i=3; i<=check; i+=2)
		{
			if(j%i==0)
			{
				fPrimeFound=false;
				break;
			}
		}

		if(fPrimeFound)
		{
			//printf("%d ", j);
			count++;
		}
		j++;
	}
}

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 < n)
	{
		// If its divisible by 2 or by 3
                                   //  its not a prime
		if(j&1==0 || j%3==0)
		{
			j++;
			continue;
		}

		int check = (int)sqrt(double(j));
		bool fPrimeFound=true;
		int incr=4;
		for(int i=5; i<=check; i+=incr)
		{
			incr=incr==2?4:2;
			if(j%i==0)
			{
				fPrimeFound=false;
				break;
			}
		}

		if(fPrimeFound)
		{
			//printf("%d ", j);
			count++;
		}
		j++;
	}
}

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