C Program to Check Whether a Number is Prime or not efficient way

September 6, 2022

In this article, you will learn C Program to Check Whether a Number is Prime or not using the efficient way.

A prime number is a positive natural number that is divisible only by 1 and itself. That means it can have only two factors 1 and the number itself.  For example: 2, 3, 5, 7, 11, 13, 17.

The following C programming topics are the primary prerequisites for this example code :

 

Problem statement:

Given a positive integer num. You need to write a C program to check if the number is prime or not.

Solution:

I am dividing the solution into the following steps.

Step 1 → Take the number n.

Step 2 → Number should be greater than 1.

Step 3 → Divide the number n with (2, n-1) or (2, n/2) or (2, sqrt(n)).

Step 4 → If the number n is divisible by any number between (2, n-1) or (2, n/2) or (2, sqrt(n)) then it is not prime

Step 5 → If it is not divisible by any number between (2, n-1) or (2, n/2) or (2, sqrt(n)) then it is a prime number

 

 

// C program to check if a
// number is prime
#include <stdio.h>
#include <math.h>

int main()
{
    int num, i, isPrimeNum = 1;

    //Ask user for input
    printf("Enter a number: = ");

    //Get the integer input from the user
    scanf("%d", &num);

    // -ve, 0 and 1 are not prime numbers
    // change isPrimeNum to 1 for non-prime number
    if ((num <= 0) || (num == 1))
    {
        isPrimeNum = 0;
    }
    else
    {
        // Iterate from 2 to sqrt(num)
        for (i = 2; i <= sqrt(num); i++)
        {
            // If num is divisible by any number between
            // 2 and num/2, it is not prime
            if ((num % i) == 0)
            {
                isPrimeNum = 0;
                break;
            }
        }
    }

    //Now print the message
    if (isPrimeNum == 1)
    {
        printf("%d is a prime number\n", num);
    }
    else
    {
        printf("%d is not a prime number\n", num);
    }

    return 0;
}

Output:

Enter a number: = 7
7 is a prime number

 

Explanation:

The above-mentioned C program to check whether a number is prime or not is an efficient way to check prime numbers.

Why I am saying this because here we only iterate through all the numbers starting from 2 to sqrt(N) beside that 2 to N.

As you know that prime number is only divisible by 1 and itself; so in each iteration, we check the number “num” is divisible by “i” or not by using the below code.

for (i = 2; i <= sqrt(num); i++)
{
    // If num is divisible by any number between
    // 2 and num/2, it is not prime
    if ((num % i) == 0)
    {
        isPrimeNum = 0;
        break;
    }
}

 

If “num” is perfectly divisible by “i“, num is not a prime number. Also marked the flag “isPrimeNum” is set to 1 and terminates the loop using the break statement. The default value of the flag isPrimeNum is 0.

 

Recommended Articles for you: