Check Prime no. Use by looping

#include <stdio.h>

// Function to check if a number is prime using recursion
int isPrime(int num, int i) 
{
    // Base cases
    if (num <= 2) 
{
        if (num == 2) 
{
            return 1;  // 2 is a prime number
        } else {
            return 0;  // Numbers less than 2 are not prime
        }
    }
    
    if (num % i == 0) 
{
        return 0;  // If num is divisible by i, it's not prime
    }

    if (i * i > num) 
{
        return 1;  // If no divisors are found, num is prime
    }

    // Recursive call: increment i to check the next possible divisor
    return isPrime(num, i + 1);
}

int main() 
{
    int num;

    // Input the number from user
    printf("Enter a positive integer: ");
    scanf("%d", &num);

    // Check if the number is prime and print result
    if (isPrime(num, 2)) {
        printf("%d is a prime number.\n", num);
    } 
	else 
    {
        printf("%d is not a prime number.\n", num);
    }

    return 0;
}

*example–

->Enter a positive integer: 29
=29 is a prime number

*explanation

1) isPrime Function:

=This function takes two arguments: the number num and a divisor i that starts from 2.
=Base Case 1: If the number num is less than or equal to 2:
=If num is 2, it’s a prime number, so return 1 (true).
=If num is less than 2 (such as 0 or 1), it’s not prime, so return 0 (false).
=Base Case 2: If num is divisible by i, meaning num % i == 0, then num is not prime, and we return 0 (false).
=Base Case 3: If i * i exceeds num, it means we’ve checked all possible divisors up to the square root of num, and since no divisors were found, we return 1 (true), declaring num as prime.
=Recursive Call: The function calls itself, incrementing i by 1 each time to check the next possible divisor.

2) Main Function:

=The user is prompted to input a number.
=The is Prime function is called with the user input and 2 as the starting divisor.
=Based on the result of the is Prime function, a message is printed to indicate whether the number is prime or not.

*How Recursion Works

Recursion means that a function calls itself until a specific condition is met. In this program, we recursively check for divisors of the input number. The base cases ensure that the recursion terminates when either:

• The number is determined to be not prime (by finding a divisor).
  All potential divisors have been checked and no divisors have been found, confirming that the number is prime.

*Example Walkthrough

Let’s check if 29 is prime:

=First, is Prime(29, 2) is called. Since 29 is not divisible by 2 and 2 * 2 is not greater than 29, the recursion continues.
=Then is Prime(29, 3) is called. Since 29 is not divisible by 3 and 3 * 3 is not greater than 29, the recursion continues.
=The process repeats for i = 4 and i = 5.
=Finally, is Prime(29, 6) is called. Since 6 * 6 (which is 36) is greater than 29, the function returns 1, meaning 29 is prime.

*Thus, the program correctly identifies 29 as a prime number.

By using recursion, the program efficiently checks divisibility up to the square root of the input number.