TEKPOOL

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 < n)
	{
		int check = (int)sqrt(double(j));
		bool fPrimeFound=true;
		for(int i=2; i<=check; i++)
		{
			if(j%i==0)
			{
				fPrimeFound=false;
				break;
			}
		}
		if(fPrimeFound)
		{
			//printf("%d ", j);
			count++;
		}
		j++;
	}
}