2

I'm currently learning c++ for the first time and I've written a cpp bool function to find if an integer is a prime number.

The code was:

bool isPrime(int n) { 
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
        else
            return true;
    }
}

However, it turns out that 9 is also considered as a prime number with this function.

I found a solution just by removing the else statement,

bool isPrime(int n) { 
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
}

but I still don't get why the else statement had anything to do with it in the first place. Can anyone help me out?

Martin G
  • 17,357
  • 9
  • 82
  • 98
Lydia
  • 81
  • 3
  • 1
    You need the `return true` to be outside the `for` loop. If all checks fail than it's true. The `else` statements means it returns true the first time the test fails. – Matt Apr 12 '18 at 02:52
  • And you only need to check up to `n/2` – Matt Apr 12 '18 at 02:52
  • second version is missing `return true` at the end. – Marek R Apr 12 '18 at 02:54
  • 2
    @Matt `sqrt(n)` – 273K Apr 12 '18 at 02:57
  • `9%2` is `1`. So, on the first iteration of the loop, the first code returns `true` when `i == 2`. More generally, the first code only ever checks `i` with a value of `2`, and immediately returns. The loop is never executed for `i` with values greater than `2`. The second version runs through all loop iterations, before concluding that a value is prime. – Peter Apr 12 '18 at 02:57
  • @S.M - better `isqrt(n)` - where `isqrt()` is specified as being the largest integer less than or equal to the square root. There are plenty of algorithms for computing `isqrt()` without use of floating point. – Peter Apr 12 '18 at 02:59
  • There are undoubtedly other questions that this could be made a duplicate of. – Jonathan Leffler Apr 12 '18 at 04:01
  • Why is this a duplicate ? She's not asking how to find prime numbers, she is asking what is wrong with her approach. – Sid S Apr 12 '18 at 05:21

4 Answers4

1

Because of the if statement.

    if (n % i == 0)
        return false;
    else
        return true;

The condition reads "if n is divisible by the current number". The condition will either be true (in which case n is not prime) or false (it might be prime) so one of the branches must be taken and the function will exit in either case, possibly prematurely.

Removing the else prevents early return, however, it also prevents true being returned by the function. You can simply add return true to the end of the function:

bool isPrime(int n) { 
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;    // must be prime
}
mhawke
  • 84,695
  • 9
  • 117
  • 138
1

Because it will return in the first loop! When the function enters the else, it will return true. Any odd number will return true — and 9 is the first odd number bigger than 1 which is not a prime.

Try this:

bool isPrime(int n) { 
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
        else
            continue;
    }
    return true;
}
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Ricardo Ribeiro
  • 11
  • 4
1

The only way a number is prime is when the loop completes, so the return true; statement should be outside the loop. You only have to check numbers up to the square root of n.

Also, you need to handle the case where n is less than 2.

#include <cmath>

bool isPrime(int n)
{
    if (n < 2)
    {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}
Sid S
  • 6,037
  • 2
  • 18
  • 24
  • 1
    It's probably better to precalculate `sqrt(n)` to ensure that it is not recalculated on each iteration. That said, the gain in performance over the original code is so dramatic that it wouldn't matter all that much — and a good optimizer might hoist the `sqrt()` call out of the loop — but it is probably better not to assume that it will. – Jonathan Leffler Apr 12 '18 at 03:10
  • @JonathanLeffler, That's a valid point, although I think most compilers will take care of it. I guess the loop header could be written as `for (int i = sqrt(n); i > 1; i--)`. I think that would add more confusion than necessary considering the question that was asked, though, – Sid S Apr 12 '18 at 03:43
  • You want to start at the small end; more numbers are multiples of 2 and 3 than are multiples of 29 and 31 (at least for computers and finite arithmetic — infinities are funny things). Another optimization is to check for even outside the loop, and then have the loop only increment over odd numbers from 3. Or you can check 2 and 3 outside the loop and then only check values of the form 6N±1 (for N = 1, 2, …). Etc. These do fewer modulo operations. – Jonathan Leffler Apr 12 '18 at 03:47
  • Another good point, but it also serves to illustrate what I just said - this is quickly getting way too complicated for the question at hand. – Sid S Apr 12 '18 at 03:49
  • Agreed, and it isn't fair to pick on only your answer because others have the same (or at least similar) issues. Actually, two of them don't even have the `sqrt()` optimization, which makes a fantastic difference even when the numbers being checked are quite small. The other changes are definitely second-order improvements. – Jonathan Leffler Apr 12 '18 at 03:50
0

9 is odd. Which means it's not divisible by 2. In fact it's the first odd number after 1 that is not prime. Your code explicitly returns true if n is not divisible by 2.

for (int i = 2; i < n; i++) {
    if (n % i == 0)
        return false;
    else
        return true;
}

The first time the for loop runs, i is 2. Either n % i == 0 is true or it is false. If true, your function immediately returns false. If false, your function immediately returns true.

You need to move the return true statement outside the loop. Only after checking all possible divisors by completing the for loop do you know if the number n is prime.

MFisherKDX
  • 2,840
  • 3
  • 14
  • 25