C Program to Determine Whether a Number is Prime

by

Checking whether a number is prime is a common programming task that helps understand loops, conditionals, and optimization techniques in C. This article will cover various C Program to Determine Whether a Number is Prime. We will explore multiple examples, each demonstrating a different approach to solve the problem. Additionally, we will discuss the prerequisites, provide detailed explanations for each example, and conclude with a summary of what we’ve learned.

Prerequisites

Before we delve into the examples, ensure you have the following prerequisites:

  • A C compiler (such as GCC)
  • A text editor or IDE for writing your C code
  • Basic understanding of C programming concepts, especially loops and conditionals

1. Checking Whether a Number is Prime

In this section, we will look at several methods to check whether a number is prime in C.

1.1 Using a Simple Loop

Example 1: Check Prime Using a Simple Loop

This method uses a simple loop to check if a number is prime.

Code

C
#include <stdio.h>

int main() {
    int num, isPrime = 1;

    printf("Enter an integer: ");
    scanf("%d", &num);

    if (num <= 1) {
        isPrime = 0;
    } else {
        for (int i = 2; i <= num / 2; ++i) {
            if (num % i == 0) {
                isPrime = 0;
                break;
            }
        }
    }

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

    return 0;
}

Explanation

  • Include necessary header: #include <stdio.h> for input/output functions.
  • Input the number: scanf reads an integer from the user.
  • Check if the number is prime: Use a loop to check divisibility from 2 to num/2.
  • Output the result: printf displays whether the number is prime or not.

Output

C
Enter an integer: 17
17 is a prime number.

1.2 Using Square Root Optimization

Example 2: Check Prime Using Square Root Optimization

This method uses square root optimization to reduce the number of iterations needed to check if a number is prime.

Code

C
#include <stdio.h>
#include <math.h>

int main() {
    int num, isPrime = 1;

    printf("Enter an integer: ");
    scanf("%d", &num);

    if (num <= 1) {
        isPrime = 0;
    } else {
        for (int i = 2; i <= sqrt(num); ++i) {
            if (num % i == 0) {
                isPrime = 0;
                break;
            }
        }
    }

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

    return 0;
}

Explanation

  • Include necessary headers: #include <stdio.h> for input/output functions and #include <math.h> for mathematical functions.
  • Input the number: scanf reads an integer from the user.
  • Check if the number is prime using square root optimization: Use a loop to check divisibility from 2 to sqrt(num).
  • Output the result: printf displays whether the number is prime or not.

Output

C
Enter an integer: 25
25 is not a prime number.

1.3 Using a Function

Example 3: Check Prime Using a Function

This method encapsulates the logic to check if a number is prime in a separate function for better modularity.

Code

C
#include <stdio.h>
#include <math.h>

int isPrime(int num);

int main() {
    int num;

    printf("Enter an integer: ");
    scanf("%d", &num);

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

    return 0;
}

int isPrime(int num) {
    if (num <= 1)
        return 0;
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

Explanation

  • Include necessary headers: #include <stdio.h> for input/output functions and #include <math.h> for mathematical functions.
  • Declare a function: int isPrime(int num) to check if a number is prime.
  • Input the number: scanf reads an integer from the user.
  • Call the function: isPrime(num) checks if the number is prime.
  • Output the result: printf displays whether the number is prime or not.

Output

C
Enter an integer: 31
31 is a prime number.

1.4 Using Recursion

Example 4: Check Prime Using Recursion

This method uses recursion to check if a number is prime.

Code

C
#include <stdio.h>
#include <math.h>

int isPrime(int num, int divisor);

int main() {
    int num;

    printf("Enter an integer: ");
    scanf("%d", &num);

    if (isPrime(num, 2))
        printf("%d is a prime number.\n", num);
    else
        printf("%d is not a prime number.\n", num);

    return 0;
}

int isPrime(int num, int divisor) {
    if (num <= 1)
        return 0;
    if (divisor > sqrt(num))
        return 1;
    if (num % divisor == 0)
        return 0;
    return isPrime(num, divisor + 1);
}

Explanation

  • Include necessary headers: #include <stdio.h> for input/output functions and #include <math.h> for mathematical functions.
  • Declare a recursive function: int isPrime(int num, int divisor) to check if a number is prime.
  • Input the number: scanf reads an integer from the user.
  • Call the recursive function: isPrime(num, 2) checks if the number is prime.
  • Output the result: printf displays whether the number is prime or not.

Output

C
Enter an integer: 29
29 is a prime number.

1.5 Using Sieve of Eratosthenes

Example 5: Check Prime Using Sieve of Eratosthenes

This method uses the Sieve of Eratosthenes algorithm to find all prime numbers up to a given number and then checks if the number is prime.

Code

C
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

void sieveOfEratosthenes(int n, bool isPrime[]);

int main() {
    int num;

    printf("Enter an integer: ");
    scanf("%d", &num);

    if (num <= 1) {
        printf("%d is not a prime number.\n", num);
        return 0;
    }

    bool isPrime[num + 1];
    sieveOfEratosthenes(num, isPrime);

    if (isPrime[num])
        printf("%d is a prime number.\n", num);
    else
        printf("%d is not a prime number.\n", num);

    return 0;
}

void sieveOfEratosthenes(int n, bool isPrime[]) {
    for (int i = 0; i <= n; i++)
        isPrime[i] = true;

    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p <= sqrt(n); p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }
}

Explanation

  • Include necessary headers: #include <stdio.h> for input/output functions, #include <stdbool.h> for boolean type, and #include <math.h> for mathematical functions.
  • Declare a function: void sieveOfEratosthenes(int n, bool isPrime[]) to implement the Sieve of Eratosthenes algorithm.
  • Input the number: scanf reads an integer from the user.
  • Call the sieve function: sieveOfEratosthenes(num, isPrime) marks all primes up to the given number.
  • Output the result: printf displays whether the number is prime or not.

Output

C
Enter an integer: 20
20 is not a prime number.

2. Conclusion

In this article, we explored various methods to check whether a number is prime in C: using a simple loop, using square root optimization, using a function, using recursion, and using the Sieve of Eratosthenes. Each method demonstrates different aspects of handling loops, recursion, and number manipulation in C programming. By understanding these methods, you can choose the one that best fits your specific needs and enhance your skills in basic programming logic and algorithm implementation in C.