Checking if a number is prime

Is there a better way to check if a number is a prime?

#include 
#include 

using namespace std;

bool doAgain();
bool isPrime(int num);

int main()
{
    do {
        int num = 0;
        do {
            cout > num;
        } while(num > again;
        if(again == 'Y') {
            return true;
        } else if(again == 'N') {
            return false;
        }
    }
}

bool isPrime(int num) {
    if(num < 2) {
        return false;
    } else if(num == 2) {
        return true;
    } else if(num % 2 == 0) {
        return false;
    }
    for(int i = 3, max = sqrt(num); i < max; i += 2) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}

Unfortunately, your isPrime function returns incorrect results for the squares of odd numbers.

This is a pretty common oversight though, so don't feel too bad.

A better implementation of isPrime looks more like this:

bool isPrime(int num) {
    if (num  1;
    } else if (num % 2 == 0 || num % 3 == 0) {
        return false;
    } else {
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

In the first if, we handle the special cases of 0 through 3 as well as all of the negative numbers.

In the second, we eliminate all of the multiples of 2 and 3.

Finally, in the catch-all else, we're handling everything else.

By starting at 5 and incrementing by 6, we're able to skip all of our multiples of 2 and 3 which we already eliminated. So we're checking 2/3rds of the numbers your original implementation checks.

Moreover, because we're dealing with integers, i * i <= num is a bit better than i < sqrt(num) (which actually needs to be <=).

StackExchange Code Review Q#84052, answer score: 15