C programming - Checking prime number

Question

I am trying to check whether a given number is prime but I've run into an issue. This is the code:

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool isPrime(int input)
{
    for (int i = sqrt(input); i >= 2; i--)
    {
        if (input % i == 0)
        {
            return false;
        }
    return true; 
    }
    
}

int main()
{
    int input;
    scanf("%d", &input);
    
    if (isPrime(input))
    {
        printf("Is prime number");
    } else
    {
        printf("Is not prime number");
    }
    
    return 0;
}

In the code block of my isPrime function, if I put return true; in the for loop like above, this will be wrong in some cases (for example, when input is 10, it will declare that 10 is a prime number). But if I put return true; outside the for loop, it works fine. So what is the difference?

Answer 1

Let's walk through your loop:

for (int i = sqrt(input); i >= 2; i--)
{

If the input is 10, then i starts out as 3 (remember that when assigning a floating-point value to an int, the fractional portion is discarded). 3 is greater than or equal to 2, so the loop body executes.

    if (input % i == 0)
    {

The remainder of 10 divided by 3 is not zero, so we do not enter the body of the if statement.

        return false;
    }
return true; 
}

And then we immediately return true.

Because of this, no matter what input you provide, your loop will only iterate 1 time. If input is evenly divisible by the integer value of its square root (such as 9, 16, or 25), then the body of the if statement is executed and it returns false, otherwise it unconditionally returns true.

For your function to work properly, you must move the return true; statement outside the body of the loop - you should only return true when you've exhausted all values of i between sqrt(input) and 2.