C Program to Check if Nth Fibonacci Number is Prime

This C program calculates the Nth Fibonacci number and checks whether it is a prime number using separate functions for Fibonacci generation and prime checking.

Concept Overview

The Fibonacci series is a sequence where each number is the sum of the previous two. Prime numbers are numbers greater than 1 that have no divisors other than 1 and themselves. This program combines both concepts to check if a particular Fibonacci term is prime.

Program

#include <stdio.h>

// Function to check if a number is prime
int isPrime(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int n, t1 = 0, t2 = 1, nextTerm;

    printf("Enter the number of terms in Fibonacci series: ");
    scanf("%d", &n);

    printf("Prime numbers in the first %d Fibonacci terms:\n", n);

    for(int i = 1; i <= n; i++) {
        if (i == 1) nextTerm = t1;
        else if (i == 2) nextTerm = t2;
        else {
            nextTerm = t1 + t2;
            t1 = t2;
            t2 = nextTerm;
        }

        if(isPrime(nextTerm)) {
            printf("%d\n", nextTerm);
        }
    }

    return 0;
}

Output

Enter the number of terms in Fibonacci series: 10
Prime numbers in the first 10 Fibonacci terms:
2
3
5
13

Explanation

• `isPrime(int n)` – Checks if the number n is prime by testing divisibility from 2 up to the square root of n.
• In the `main` function, we generate Fibonacci numbers iteratively and check each term for primality.
• The program prints all prime Fibonacci numbers within the first n terms.

Sample Output

Enter the number of terms in Fibonacci series: 15
Prime numbers in the first 15 Fibonacci terms:
2
3
5
13
89

Additional Notes

The program can be modified to check for primality of Fibonacci numbers beyond the first n terms by adjusting the loop and Fibonacci generation logic. Additionally, for larger Fibonacci numbers, consider using a more efficient prime-checking algorithm or data type to handle larger integers.

Alternative Approach

Instead of generating Fibonacci numbers iteratively, we can also use a recursive function to find the Nth Fibonacci number and then check if it is prime. However, the iterative approach is more efficient for larger values of n due to reduced function call overhead.

#include <stdio.h>

// Function to calculate the nth Fibonacci number
int fibonacciNumber(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return fibonacciNumber(n - 1) + fibonacciNumber(n - 2);
}

// Function to check if a number is prime
int isPrime(int num) {
    if (num <= 1) return 0;
    for (int i = 2; i*i <= num; i++) {
        if (num % i == 0) return 0;
    }
    return 1;
}

int main() {
    int n;
    printf("Enter the element of fibonacci to be checked: ");
    scanf("%d", &n);

    int fibNum = fibonacciNumber(n);
    printf("Fibonacci number %d\n", fibNum);

    if (isPrime(fibNum))
        printf("%d element of fibonacci series is a prime number\n", n);
    else
        printf("%d element of fibonacci series is not a prime number\n", n);

    return 0;
}

Output

Enter the element of fibonacci to be checked: 7
Fibonacci number 13
7 element of fibonacci series is a prime number

Explanation

• `fibonacciNumber(int n)` – A recursive function that calculates the nth Fibonacci number.
• `isPrime(int num)` – Checks if the given number is prime by testing divisibility.
• The program first calculates the Fibonacci number for the given n and then checks if it is prime, printing the results accordingly.

Conclusion

This program effectively demonstrates how to combine the concepts of Fibonacci series and prime number checking in C. It serves as a good exercise for understanding loops, functions, and conditional statements in C programming.

Further Exploration

You can extend this program to find all prime Fibonacci numbers up to a certain limit or to check for primality of Fibonacci numbers generated using different methods (e.g., matrix exponentiation). Additionally, exploring more efficient algorithms for prime checking can enhance the performance of the program.

Final Note

Remember that while this program is suitable for educational purposes, it may not be the most efficient way to check for large Fibonacci numbers or their primality. Always consider the trade-offs between simplicity and performance when writing code.