C Program to Check Prime Number

Prime numbers are those natural numbers which has exactly two factors : 1 and itself. If a number has factors more than two, they are composite. 1 and 0 are neither prime nor composite. C program to determine if a given number is prime or not is shown below:

Example 1: Program to Check Prime Number 

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

int main()
{
    int n,i,f=0;
    printf("Enter a number : ");
    scanf("%d",&n);

    if(n < 2)
        printf("%d is neither prime nor composite",n);
    else
    {
        for(i=2; i<=(int)pow(n,0.5); i++)
        {
            if (n % i == 0)
                f=f+1;
        }
        if (f > 0)
            printf("%d is composite",n);
        else
            printf("%d is prime",n);
    }
    
    return 0;
}

Here, the number entered by user is stored in integer variable n. Variable f is used to hold number of factors and i is used while looping. To determine whether a number is prime or not, we need to find at least one factor of that number which is neither 1 nor itself. We need to check for that factor starting from 2 to integer part of square root of that number.


Consider 10, the square root of 10 is 3.162. Now, just take the integer part i.e. 3. If we could find a factor for 10 from 2 to 3 then 10 is not a prime number. Here 2 is a factor of 10, so it is not prime. In this way the algorithm works for all possible number.

Output

Enter a number : 21
21 is composite

Enter a number : 29
29 is prime