7
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 3
    \$\begingroup\$ one minor comment, <math.h> is a C library so you should be using <cmath> since I see you have a tag of C++. \$\endgroup\$
    – arsenal
    Mar 14 '15 at 0:51
  • 6
    \$\begingroup\$ What does isPrime(9) return? \$\endgroup\$
    – nhgrif
    Mar 14 '15 at 0:55
  • \$\begingroup\$ @nhgrif false \$\endgroup\$
    – Happy Time
    Mar 14 '15 at 0:58
  • 2
    \$\begingroup\$ Your doAgain() function should accept lowercase letters. \$\endgroup\$
    – Cole Tobin
    Mar 14 '15 at 7:09
  • 11
    \$\begingroup\$ @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. \$\endgroup\$
    – gnasher729
    Mar 14 '15 at 9:01
15
\$\begingroup\$

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 <=).

\$\endgroup\$
5
  • \$\begingroup\$ Whoops, sorry, I meant <= in my code. \$\endgroup\$
    – Happy Time
    Mar 14 '15 at 1:24
  • \$\begingroup\$ isPrime(49) returns true. You can change the increment to i += 2 and it works. \$\endgroup\$
    – Happy Time
    Mar 14 '15 at 2:18
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – nhgrif
    Mar 14 '15 at 12:10
  • 1
    \$\begingroup\$ 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) \$\endgroup\$
    – derobert
    Mar 14 '15 at 13:54
  • \$\begingroup\$ @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. \$\endgroup\$
    – nhgrif
    Mar 14 '15 at 14:30
8
\$\begingroup\$
  • 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.

  • <math>, 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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – nhgrif
    Mar 14 '15 at 1:22
  • 1
    \$\begingroup\$ This answer would be better if your link were more fleshed out within the answer. Links can die. \$\endgroup\$
    – nhgrif
    Mar 14 '15 at 1:22
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

In the code there are else clauses that are unnecessary. The if statements above them return.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – mdfst13
    Apr 21 '16 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.