C program to check whether a number is prime or not

Question

I used the following code and it showed numbers like 49 as prime and not composite. I am new to programming so please help me with the correct code.

#include <stdio.h>
int main()
{
    int n;
    int i;
    scanf ("%d", &n);
    for (i=2; i<n; i++)
    {
        if (n%i==0)
        {
            printf ("number is composite");
        }
        else
        {
            i=i+1;
        }  
    }
    printf("number is prime");
    return 0;

}

Answer 1

You didn't stop the loop when you discovered that the number was composite, so composite numbers get both messages.

When i is not a factor of n you are adding 1 to i but then the for loop adds 1 again. This means that for every number that is not a factor of n you skip a number.

The printf("number is prime"); is not surrounded by any kind of if, so it will always be printed regardless of whether or not the number is actually prime. Unlike humans, computers won't think twice about printing conflicting information because computers are incapable of interpreting the actions we make them do.

You can optimize your code by checking less numbers. Only check up to the square root of the number.

This code is untested but should work. Note that this only eliminates the checking of factors above the square root, but not any multiples of previously checked factors (e.g. written like this, the program will check if the number is divisible by 2 but also by 4, 6, 8, 10, etc).

#include <stdio.h>
#include <math.h>
int main()
{
    int n;
    int i;
    int isComposite = 0;
    scanf ("%d", &n);
    for (i = 2; i <= (int)sqrt((double)n); i++){
        if (n % i == 0){
            printf ("number is composite");
            isComposite = 1;
            break;
        }
    }
    if (!isComposite){
        printf("number is prime");
    }
    return 0;

}