This message was edited by Lundin at 2007-3-15 3:31:33

---

: : : :

: : : : bool isPrime(const int& x)
: : : : {
: : : :   if(x == 2)
: : : :     return true;
: : : :   else if(x <= 1)
: : : :     return false;
: : : :   
: : : :   else if(x % 2 == 0)
: : : :     return false;
: : : : 
: : : : 
: : : :   for (int i=3; i<x/2; i+=2)
: : : :   {
: : : :     if (x % i == 0) 
: : : :       return false;
: : : :   }
: : : : 
: : : :   return true;
: : : : }
: : : : 

: : : :
: : : : 1 is not a prime number. Plus, prime numbers are natural numbers, thus not anything like 0, -1, -2, -3...
: : :
: : : Thanks for your correction. Indeed, negatives are not prime, but it depends on your definition if one is prime. From the WikiPedia ([[http://en.wikipedia.org/wiki/1_%28number%29]]):
: : :
: : : 'One is currently considered neither a prime number, nor a composite number - although it used to be considered prime.'
: : :
: : : See ya,
: : : bilderbikkel
: : :
: : :
: :
: :
: :
: : In that case, x and i should be changed to unsigned int.
: :
: : Another comment: there is no point in passing x as reference. As a rule of thumb, pass primitive data types (int, char, float etc) by value and everything else by reference.
: :
:
: My comment is that the for loop the condition should be stored in a constant varible or something as every time it tests the condition it is dividing x by two. Where as, if it were to store the test condition in a const int or whatever it would eliminate this process mind you it is completely irrevelent really and it is somewhat easier to read without it
:


Yeah but it is a good point that I didn't think of. It will increase the efficiency of the code drastically. Here is a new version with correct data types and no reference.

bool isPrime(unsigned int x)
{
  if(x == 2)
    return true;
  else if(x < 2)
    return false;
  else if(x % 2 == 0)
    return false;


  unsigned int half_x = x / 2;
  unsigned int i;

  for(i=3; i<half_x; i+=2)
  {
    if (x % i == 0) 
      return false;
  }

  return true;
}