Prime Number Program in C

What is Prime Number in C?

A prime number is a natural number that is greater than 1 and is only divisible by 1 and itself. In other words, no number except the number itself, and 1 can divide a prime number.

Example: 2, 3, 5, 7, 11, 13, 17, 19 …., etc.

Write a C program to check if a given number is Prime number. If the number is Prime, then display it is a prime number else display it is not a prime number.

1. Take a number as input.
2. Check if the number is divisible by any of the natural numbers starting from 2.
3. If it is, then it is not a prime number. Otherwise, it is a prime number.
4. Exit.

There are several ways to write a prime number program in C language. Let’s look at all different techniques to write a prime number program.

• Prime Number Program in C using Loops (Naive Approach)
• Prime Number Program in C using Optimized Approach
• Prime Number Program in C using Recursion
• C Program to Find Prime Numbers in a Given Range
• C Program to Generate Prime Numbers Using Sieve of Eratosthenes
• C Program to Generate Prime Numbers Using Sieve of Sundaram

The idea of this naive solution is to iterate a loop from 2 to N/2. If we iterate the loop from 2 to N/2, then we cover all the factors that could divide the number. Therefore, we iterate the loop till N/2 for checking whether a number is prime or not.

Examples:

• N=11, the loop will run from 2 to 5(N/2) = 2,3,4,5. If we divide the number 11 by any of these numbers (2,3,4,5) we will not get remainder equal to 0. Therefore our output will be “11 is a prime number”.
• N=15, the loop will run from 2 to 7(N/2) = 2,3,4,5,6,7. If we divide the number 15 by 3 we will get remainder equal to 0 which means 15 has a factor other than 1 and 15. Therefore, our output will be “15 is not a prime number”.

Here is the source code of the C program to check if a given Number is prime number or not using a naive approach. The C Program is successfully compiled and run on a Linux system. The program output is also shown below.

1. Take a number as input and store it in the variable num.
2. If the number is lesser than or equal to 1, then print the output as “It is not a prime number“.
3. Initialize the variable flag to zero.
4. Using for loop, check if the input number is divisible by any of the natural numbers starting from the digit 2.
5. If it is, then assigns the variable flag with 1.
6. Print the output as “It is a prime number“, if the variable flag==0.
7. Otherwise print the output as “It is not a prime number” and exit.

Time Complexity: O(n)
The above program for checking whether a number is prime or not has a time complexity of O(n/2) = O(n) as the loop runs from 2 to n/2, where n is the number given as input.

Space Complexity: O(1)
In this program we are not initializing any array or other data types that takes lot of storage. We are just initializing the variable. Therefore, our space complexity is constant, i.e. O(1).

Testcase 1: In this case, we enter the number “11” as input to check whether it is a prime number or not.

Enter a number:
11
11 is a prime number

Testcase 2: In this case, we enter the number “15” as input to check whether it is a prime number or not.

Enter a number:
15
15 is not a prime number

The idea of this optimized solution is completely related to the method 1 approach. But here instead of iterating a loop from 2 to N/2, we will iterate through all the numbers starting from 2 to sqrt(N).
The reason for choosing sqrt(N) is that the factor of a number is always present between 2 to sqrt(N) and if we find a factor then we simply need to stop the iteration and print it is not a prime number else it is a prime number.

Examples:

• N=36, we need to iterate the loop from 2 to 6(sqrt(36)). If we divide the number 36 by 2, we will get remainder equal to 0 which means 36 has a factor other than 1 and 36. Therefore, our output will be “36 is not a prime number”.
• N=53, sqrt(53) = 7. So, our loop will iterate from 2 to 7. If we divide the number 53 by any of these numbers (2,3,4,5,6,7) we will not get remainder equal to 0. Therefore our output will be “53 is a prime number”.

Here is the source code of a C program to check if a given number is prime number or not using an optimized approach. The C Program is successfully compiled and run on a Linux system. The program output is also shown below.

1. Take a number as input and store it in the variable num.
2. If the number is lesser than or equal to 1, then print the output as “It is not a prime number“.
3. Initialize the variable flag to zero.
4. Iterate through all the numbers starting from 2 to sqrt(N).
5. If it is, then assigns the variable flag with 1.
6. Print the output as “It is a prime number“, if the variable flag==0.
7. Otherwise print the output as “It is not a prime number” and exit.

Time Complexity: O(sqrt(n))
The above program for checking whether a number is prime or not has a time complexity of O(sqrt(n)) as the loop runs from 2 to sqrt(n), where n is the number given as input.

Space Complexity: O(1)
In this program we are not initializing any array or other data types that takes lot of storage. We are just initializing the variable. Therefore, our space complexity is constant, i.e. O(1).

Testcase 1: In this case, we enter the number “53” as input to check whether it is a prime number or not.

Enter a number:
53
53 is a prime number

Testcase 2: In this case, we enter the number “36” as input to check whether it is a prime number or not.

Enter a number:
36
36 is not a prime number

In this method, we use the recursion to find whether the entered number is a prime number or not.

Here is the source code of the C Program to find whether a Number is Prime or Not using Recursion. The C Program is successfully compiled and run on a Linux system.

/*
 * C Program to find whether a Number is Prime or Not using Recursion
 */
 
#include <stdio.h>
 
int primeno(int, int);
 
int main()
{
    int num, check;
    printf("Enter a number: ");
    scanf("%d", &num);
    check = primeno(num, num / 2);
    if (check == 1)
    {
        printf("%d is a prime number\n", num);
    }
    else
    {
        printf("%d is not a prime number\n", num);
    }
    return 0;
}
 
int primeno(int num, int i)
{
    if (i == 1)
    {
        return 1;
    }
    else
    {
       if (num % i == 0)
       {
         return 0;
       }
       else
       {
         return primeno(num, i - 1);
       }       
    }
}

1. In this C program, we are reading the integer number using ‘num’ variable.
2. The check variable is used to call the primeno() function by passing the value of ‘num’ variable and the value of division of ‘num’ variable value by 2 as an argument.
3. The primeno() function is used to find whether the entered number is a prime number or not. If else condition statement is used to check the value of ‘i’ variable is equal to 1 and return the value of ‘i’ variable to the called variable ‘check’.
4. Otherwise, if the condition is false execute the else statement and call the primeno() function by passing the value of ‘num’ variable and the decrement the value of ‘i’ variable by 1. Return the resulted value to the called variable ‘check’.
5. If else condition statement is used to check that the value of ‘check’ variable is equal to 1.
6. If the condition is true print the statement as prime number. Otherwise, if the condition is false print the statement as not a prime number.

In this case, we enter the number “89” as input to check whether it is a prime number or not.

$ cc pgm24.c
$ a.out
Enter a number: 89
89 is a prime number

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.