I have written a findClosestPrime() in C++, but Xcode complains that "Control may reach end of non-void function"

Question

I've written a function in C++ to find the closest prime number after the input number. Let's assume the input number is larger than 100, so there is no special check for the cases when the input number is 1 or 2 or etc.

int getClosestPrime(int inputNum){
    bool isPrime = false;
    inputNum++;
    while (!isPrime){
        for (int i = 2; i <= inputNum/2; i++){
            if (inputNum % i == 0){
                isPrime = false;
                break; //if at any time found it's not a prime, break the for loop
            }
            isPrime = true;
        }
        if (isPrime == false){
            inputNum++;
        } else {
            return inputNum;
        }
    }
}

I think the logic should be good enough as I tested here on ideone: https://ideone.com/hcUpvK it's giving the right results.

However, when I use Xcode to run the code, it always complains that "Control may reach end of non-void function".

Could anybody explain? Thanks!

score 1 · Answer 1 · answered Dec 07 '17 at 10:21

If you want to avoid the warning you could change the code slightly so that XCode would be able to see that your logic is sound (which it is). It might look something like this.

int getClosestPrime(int inputNum){
    bool isPrime = false;
    inputNum++;
    while (!isPrime){
        isPrime = true; // assume the number is a prime
        for (int i = 2; i <= inputNum/2; i++){
            if (inputNum % i == 0){
                inputNum++; // go to next number
                isPrime = false; // the number is *not* a prime
                break; // done with this number
            }            
        }
    }
    return inputNum;
}

score 0 · Answer 2 · answered Dec 07 '17 at 10:11

There is a set of assignments to your variables that makes the loop finish without a return; inside the loop, the for loop may complete (i.e. inputNum / 2 is < 2), then isPrime is false, then somehow magically becomes true by the time the while loop resumes.

We know as humans that, in reality, this will never happen. You'll always end up returning inputNum unless isPrime is false, in which case you reenter the loop. However, your compiler isn't that smart - it can't work out that invariant, as it requires more complex logic than it's capable of reasoning with. So, it warns about the hypothetical case.

Most of the time, it's easier just to throw a return 0 at the end to shut it up, with a comment noting why it can never actually happen.

The problem with "return 0" to shut up the compiler is that you might be mistaken for some rare case (negative values? overflow?), or someone might change the code; and then suddenly the 0-value will propagate. Using assert or throw in cases that should not happen avoid that. Mistakes happen - e.g. this question-title says "findClosestPrime", the question says "getClosestPrime" and it finds the next prime - not closest. — Hans Olsson, Dec 07 '17 at 11:06

Martin Bonner supports Monica · Answer 3 · 2017-12-07T10:46:28.037

Note that this is a warning, not an error. The problem is that XCode cannot see that you will only ever reach the end of the loop with isPrime set false - and therefor thinks you can break out of the loop ... and reach the end of the function.

Given that isPrime doesn't actually control the loop, why not get rid of it? Also, I suggest only considering odd numbers and only testing up to the square root of the potential prime.

int getClosestPrime(int inputNum){

    // The first prime number is 2.  Any smaller inputs should return this.
    if (inputNum <= 2)
         return 2;

    inputNum |= 1; // Force input to be odd.

    while (true){
        const int limit = sqrt(inputNum);  // Only need to look for prime factors
                                           // up to the square root.
        bool isPrime = true;
        for (int i = 3; i <= limit; i+=2){ // Only look for *odd* prime factors.
            if (inputNum % i == 0){
                isPrime = false;
                break; //if at any time found it's not a prime, break the for loop
            }
        }
        if (isPrime){
            return inputNum;
        }
        inputNum += 2;
    }
}

For values of inputNum > 100, I would expect this to be about 10 times faster (and the speed-up improves as the value gets higher). Note that there are some staggeringly fast ways of testing for whether a number is prime or not. Miller-Rabin with a rather small list of numbers can deterministically check up to 2^64; using a sieve of Erothosenes to find all primes upto sqrt(2*original-input), and then only testing with those primes could be simpler to understand.

@UKMonkey : The OP specifies that `inputNum` is > 100. (Presumably in order to be able to ignore the initial sanitization). I quite like `if (inputNum < 4) return inputNum;` which is clearly correct for 2 and 3, and is not stupid for 0, 1, and negative values. — Martin Bonner supports Monica, Dec 07 '17 at 10:27
"The OP specifies that inputNum is > 100" - didn't see that ... personally I'd add assert if I was that confident, but your if statement is quite nice too — UKMonkey, Dec 07 '17 at 10:29
Actually, I decided that the first prime above (say) -27, is 2 - so return that. — Martin Bonner supports Monica, Dec 07 '17 at 10:47

I have written a findClosestPrime() in C++, but Xcode complains that "Control may reach end of non-void function"

3 Answers3