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

#include &lt;iostream&gt;
#include &lt;math.h&gt;

using namespace std;

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

int main()
{
    do {
        int num = 0;
        do {
            cout &lt;&lt; "Enter a positive integer to check: ";
            cin &gt;&gt; num;
        } while(num &lt; 1);
        if(isPrime(num)) {
            cout &lt;&lt; "Prime!!!" &lt;&lt; endl;
        } else {
            cout &lt;&lt; "Not a prime." &lt;&lt; endl;
        }
    } while(doAgain());
    cout &lt;&lt; "Bye!" &lt;&lt; endl;
}

bool doAgain() {
    while(true) {
        cout &lt;&lt; "Again? (Y/N) ";
        char again;
        cin &gt;&gt; again;
        if(again == 'Y') {
            return true;
        } else if(again == 'N') {
            return false;
        }
    }
}

bool isPrime(int num) {
    if(num &lt; 2) {
        return false;
    } else if(num == 2) {
        return true;
    } else if(num % 2 == 0) {
        return false;
    }
    for(int i = 3, max = sqrt(num); i &lt; 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 &lt;= 3) {
        return num &gt; 1;
    } else if (num % 2 == 0 || num % 3 == 0) {
        return false;
    } else {
        for (int i = 5; i * i &lt;= 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 &lt;= num is a bit better than i &lt; sqrt(num) (which actually needs to be &lt;=).