trjhtr

I've seen 2 versions of an algorithm for determining the primality of a number, and I think the first one is better, as you skip all the even numbers(I know they're almost the same thing, just wondering if the first one is any better). Which version is generally better?

bool is_prime1(int x)
 x % 2 == 0)
 return false;

 int p = sqrt(x);
 for (int i = 3; i <= p; i += 2)
 if (x % i == 0)
 return false;

 return true;

bool is_prime2(int x)

 if (x == 1)
 return false;

 int p = sqrt(x);
 for (int i = 2; i <= p; ++i)
 if (x % i == 0)
 return false;

 return true;

At least when I've timed things, code like the first was generally faster than the second. The obvious way to check this is to simply time both for various input values--faster is an objective measurement, so there's not a lot of question about the right answer.

There is still room for further improvement in many cases though. First of all, the call to sqrt looks fairly innocent, but is often quite slow. In any cases, it's faster to do something like this instead:

for (int i = 3; i * i <= x; i += 2)

Again, the only way to be sure is to time it though.

Depending on your situation, it can also be worth using a sieve of Eratosthenes to find candidate primes, and only do trial division by those candidates. This won't typically help (much, anyway) for smaller numbers, but above some threshold it tends to become more useful.

The biggest problem I see other than that is just names. For example, I'd prefer something like candidate_divisor instead of i and candidate_prime instead of x. For a function this tiny it's unlikely to make a huge difference though.