# 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++. Commented Mar 14, 2015 at 0:51
• What does isPrime(9) return? Commented Mar 14, 2015 at 0:55
• @nhgrif false Commented Mar 14, 2015 at 0:58
• Your doAgain() function should accept lowercase letters. Commented Mar 14, 2015 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. Commented Mar 14, 2015 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. Commented Mar 14, 2015 at 1:24
• isPrime(49) returns true. You can change the increment to i += 2 and it works. Commented Mar 14, 2015 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. Commented Mar 14, 2015 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) Commented Mar 14, 2015 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. Commented Mar 14, 2015 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. Commented Mar 14, 2015 at 1:22
• This answer would be better if your link were more fleshed out within the answer. Links can die. Commented Mar 14, 2015 at 1:22

Consider looking into sieves. Things like the sieve of erastothenes or the sieve of atkin are really really quick where it comes to finding primes.

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. Commented Apr 21, 2016 at 21:45