w3resource

C Exercises: Check a number is a prime number or not


12. Prime Check Recursion Variants

Write a program in C to check if a number is a prime number or not using recursion.

Pictorial Presentation:

C Exercises: Check a number is a prime number or not

Sample Solution:

C Code:

#include<stdio.h>

int checkForPrime(int);
int i;

int main()
{

    int n1,primeNo;

	printf("\n\n Recursion : Check a number is prime number or not :\n");
	printf("--------------------------------------------------------\n");
	
    printf(" Input any positive number : ");
    scanf("%d",&n1);
    
    i = n1/2;

    primeNo = checkForPrime(n1);//call the function checkForPrime

   if(primeNo==1)
        printf(" The number %d is a prime number. \n\n",n1);
   else
      printf(" The number %d is not a prime number. \n\n",n1);
   return 0;
}

int checkForPrime(int n1)
{
    if(i==1)
    {
        return 1;
    }
    else if(n1 %i==0)
    {
         return 0;
    }     
    else
       {
         i = i -1; 
         checkForPrime(n1);//calling the function checkForPrime itself recursively
      }
}

Sample Output:

 Recursion : Check a number is prime number or not :                                                          
--------------------------------------------------------                                                      
 Input any positive number : 7                                                                                
 The number 7 is a prime number.  

Explanation:

int checkForPrime(int n1)
{
    if(i==1)
    {
        return 1;
    }
    else if(n1 %i==0)
    {
         return 0;
    }     
    else
       {
         i = i -1; 
         checkForPrime(n1);//calling the function checkForPrime itself recursively
      }
}

The function 'checkForPrime()' takes an integer n1 as input and checks if the number is divisible by i (which is initially set to some value outside the function).

  • If i is equal to 1, the function returns 1, indicating that the number is prime.
  • If n1 is divisible by i, the function returns 0, indicating that the number is not prime.
  • Otherwise, the function decrements the value of i and calls itself recursively with the same value of n1.
  • The function continues to call itself recursively until i reaches 1 or n1 is found to be divisible by i.

Time complexity and space complexity:

The time complexity of this function is O(n) where n is the input number since the function checks all the numbers from 2 to n-1 to determine if the number is prime or not.

The space complexity is O(1) since the function uses only constant space for storing the value of i.

Flowchart:

Flowchart: Check a number is prime number or not.

For more Practice: Solve these Related Problems:

  • Write a C program to check if a number is composite using recursion.
  • Write a C program to list all prime numbers within a range using recursion.
  • Write a C program to find the next prime number after a given integer using recursion.
  • Write a C program to check for primality recursively while caching previous results.

C Programming Code Editor:



Previous: Write a program in C to convert a decimal number to binary using recursion.
Next: Write a program in C to find the LCM of two numbers using recursion.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.