Prime or Composite Number Using Recursion

Introduction

In this lab, we will learn how to write a C program that checks if a number is a prime number or a composite number using recursion. A prime number is a number that is only divisible by 1 and itself, while a composite number is a number that is not a prime number. We will use recursion to write the program, which is a technique to solve problems by breaking them down into smaller, simpler problems.

Skills Graph

Getting User Input

We will start by asking the user to enter a positive integer number to check if it's a prime number or a composite number using the scanf function. Add the following code in the main.c file inside the int main() function:

#include <stdio.h>

int main()
{
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    return 0;
}

Writing the Recursive Function for Checking the Number

In this step, we will write the recursive function to check if the number is prime or composite. This function takes two arguments - the number to check and a counter variable that starts from the number divided by 2. If the counter reaches 1, the function returns 1 which indicates that the number is prime, otherwise, the function makes a recursive call to itself with the decreased counter variable. If at any point, the number is divisible by the counter variable without any remainder, the function returns 0 which indicates that the number is composite. Add the following code at the end of the main.c file:

int isPrime(int n, int c)
{
    if (c == 1) {
        return 1;
    } else {
        if (n % c == 0) {
            return 0;
        } else {
            return isPrime(n, c - 1);
        }
    }
}

Checking and Outputting the Result

In this step, we will call the isPrime function to check if the number is prime or composite. Based on the result of the function, we will output the appropriate message to the user. Add the following code at the end of the main.c file to complete the program:

int main()
{
    int num, prime;
    printf("Enter a positive integer: ");
    scanf("%d", &num);
    prime = isPrime(num, num/2);
    if (prime == 1) {
        printf("%d is a prime number.\n", num);
    } else {
        printf("%d is a composite number.\n", num);
    }
    return 0;
}

Build and Run the Program

In this step, we will compile and run the program. Open the terminal and navigate to the directory where the main.c file is located. Add the following command in the terminal to compile the program:

gcc main.c -o main

Add the following command to run the program:

./main

Enter a positive integer number when prompted and press Enter. The program will output whether the number is a prime or composite number.

Summary

In this lab, we have learned how to write a C program that checks if a number is a prime number or a composite number using recursion. We also learned how to use the scanf function to get user input, write a recursive function to check if a number is prime or composite, and output the result to the user. Recursion is a useful technique to solve problems that involve breaking them down into smaller, simpler problems.