Thread: optimise algorithm

I have written a program which tests for prime numbers. Please could someone review my code and tell me if there is any way to optimise it as once you start hitting large numbers it takes that much longer to break the loop and return a result.

Code:

int prime( long unsigned int &number )
{
   int factor = 0;
   
   for( int i = 1; i <= number; i++ )
      if( number % i == 0 )// if there is no remainder - i is a factor of number
         factor++; 
   
   if( number == 1 )
      return 1;
   else if( factor == 2 ) // number is prime if only 2 factors are found
      return 1;
   else // more than two factors found, number is not prime
      return 0;      
} // end function prime

The code below is a very obvious optimization, there are definitely more things that could be optimized if you need more speed.

Code:

#include <math.h>

int prime( long unsigned int &number )
{
	if (number % 2 == 0)
	{
		cout << "Number is not prime\n";
		return 0;
	}
	for (int i = 3; i <= sqrt(number); i=i+2)
	{
		if (number % i == 0)// if there is no remainder - i is a factor of number
		{
			cout << "Number is not prime\n";
			return 0;
		}
	}
	cout << "Number is prime\n";
	return 0;
}

If your interested in making a faster test then read this...
http://mathworld.wolfram.com/FermatsLittleTheorem.html

The first point about the sqrt is important, however, dividing by only primes is harder then one might think. If you use an array to mark out multiples then you are limited to numbers in the int region, because too much larger then 2^32 and you won't have the RAM. Anyways, computers are fast enough these days that checking primality on a number as small as an int is very fast on even unoptimized code, which makes dividing by primes even less attractive.

Right, I agree about the sqrt() being done once outside the loop. Still, why is int i in the for loop incremented by 2 each loop?

Originally Posted by cyberCLoWn

Still, why is int i in the for loop incremented by 2 each loop?

Because other than the number 2, there are no even numbers that will be prime, so incrementing by 2 will keep you limited to odd numbers.

I never even thought about that scribbler. Thanks for the clarification.

So, what do I do about the optimization flags? (-01, etc)