C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Functions in C

Prime number check using Recursive function

C Program: Prime number check using Recursive function

C 
#include <stdio.h>


 


// Function declaration


int isPrime(int num, int i);


 


int main() {


    int number;


 


    // Input number


    printf("Enter a number: ");


    scanf("%d", &number);


 


    // Handle numbers less than 2


    if (number <= 1) {


        printf("%d is not a prime number.\n", number);


        return 0;


    }


 


    // Function call


    if (isPrime(number, 2))


        printf("%d is a prime number.\n", number);


    else


        printf("%d is not a prime number.\n", number);


 


    return 0;


}


 


// Recursive function to check divisibility


int isPrime(int num, int i) {


    if (i * i > num)  // If i exceeds sqrt(num), it's prime


        return 1;


    if (num % i == 0) // If divisible, not prime


        return 0;


    return isPrime(num, i + 1); // Check next divisor


}

Output

 
OUTPUT 1 :
Enter a number: 17
17 is a prime number.

OUTPUT 2 :
Enter a number: 20
20 is not a prime number.

Explanation

  1. isPrime(num, i) Function
    • Checks divisibility of num starting from i = 2.
    • If num is divisible by any number other than 1 and itself → Not prime.
    • Recursion continues until i * i > num (i.e., up to √num).
  2. Base Conditions
    • If i * i > num → No divisor found → Prime.
    • If num % i == 0 → Divisible → Not prime.
  3. Main Function
    • Takes number input.
    • Handles cases for 0 and 1.
    • Calls the recursive function.

 

Previous
Next