# Checking if a number is prime

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

#include <iostream>
#include <math.h>

using namespace std;

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

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

bool doAgain() {
while(true) {
cout << "Again? (Y/N) ";
char again;
cin >> 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;
}

• one minor comment, <math.h> is a C library so you should be using <cmath> since I see you have a tag of C++. Mar 14 '15 at 0:51
• What does isPrime(9) return? Mar 14 '15 at 0:55
• @nhgrif false Mar 14 '15 at 0:58
• Your doAgain() function should accept lowercase letters. Mar 14 '15 at 7:09
• @happytime: He asked what isPrime (9) returns. He didn't ask what you think it returns. The reason why he asked should have been obvious - because he spotted an obvious bug in your code and wanted you to think about it. So if you reply "false" then I guess that you didn't check it and just made up your answer. Mar 14 '15 at 9:01

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 <= 3) {
return 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 <=).

• Whoops, sorry, I meant <= in my code. Mar 14 '15 at 1:24
• isPrime(49) returns true. You can change the increment to i += 2 and it works. Mar 14 '15 at 2:18
• @happytime It doesn't. Double check the if within the for loop and make sure you copied it correctly. On the first iteration of the loop, we try 49 % 5 == 0 (which is false), but also 49 % (5 + 2) == 0 (which is true). I think you didn't copy the for loop body correctly. Mar 14 '15 at 12:10
• i * i needs to be computed many times, whereas sqrt(num) only once... so as the numbers get larger, i * i is going to be slower. (Not sure when the switch-over is) Mar 14 '15 at 13:54
• @derobert That's true. I'm more concerned about the implicit conversion to and from floating point numbers in what should be a strictly-integer problem. If i * i versus sqrt(num) is an optimization concern, then I'd recommend writing a sqrt function for integers... which not only would be better than going to and from floating points, but could also be significantly faster potentially. Mar 14 '15 at 14:30
• Do not use namespace std

• You must've got a warning that doAgain may return without a value. What happens if I answer Z to the prompt?

• To test a single number, the approach is good enough. For multiple queries (as a doAgain loop suggests) I recommend to precompute a table of primes with your favourite sieve.

• [itex], sqrt and max are not strictly necessary. i*i <= n as a loop condition is good enough.

• Using int limits your program unnecessarily. unsigned long lets you check larger numbers.

• doAgain can't return without a value. If you enter Z to the prompt, it will ask you again... and again and again until you enter Y or N. Mar 14 '15 at 1:22
Basically, you have an array of booleans called something like isPrime, and you mark off all of the numbers that are factors of something. Then you just go to the array index representing the value you want to check, and you get your answer pretty damn quick. So isPrime[3] == true and isPrime[9] == false.
In the code there are else clauses that are unnecessary. The if statements above them return.
• Hi. Welcome to Code Review! We usually add more explanation with examples from the original code and with your proposed modifications. You also may want to explain why it might be better to avoid unnecessary else clauses. Apr 21 '16 at 21:45