How to check if a number is prime in C?

Prime numbers are integers greater than 1 that have no positive divisors other than 1 and themselves. In this article, we will explore different methods to check if a number is prime in the C programming language.

Method 1: Brute Force Approach

The most straightforward method to check if a number is prime is to use a brute-force approach.

We can iterate from 2 to the square root of the number and check if the number is divisible by any of these values.

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

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int num;
    printf("Enter a number: ");
    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;
}

This code defines a function isPrime that takes an integer n as input and returns true if it is prime and false otherwise.

The main function takes user input and calls the isPrime function to determine whether the entered number is prime.

Method 2: Optimized Brute Force

While the brute-force approach is simple, it can be optimized to reduce unnecessary iterations.

For instance, we can skip even numbers greater than 2 since they are divisible by 2.

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

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    if (n == 2) {
        return true;
    }

    if (n % 2 == 0) {
        return false;
    }

    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    int num;
    printf("Enter a number: ");
    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;
}

This optimized version eliminates the need to check even divisors greater than 2, significantly reducing the number of iterations.

Method 3: Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit.

While it's commonly used for generating a list of primes, we can adapt it to check if a single number is prime.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    // Create an array to store prime flags
    bool* primes = (bool*)malloc((n + 1) * sizeof(bool));

    // Initialize all elements as true
    for (int i = 0; i <= n; i++) {
        primes[i] = true;
    }

    // Mark non-prime numbers
    for (int p = 2; p * p <= n; p++) {
        if (primes[p] == true) {
            for (int i = p * p; i <= n; i += p) {
                primes[i] = false;
            }
        }
    }

    // Check if n is prime
    bool result = primes[n];

    // Free the allocated memory
    free(primes);

    return result;
}

int main() {
    int num;
    printf("Enter a number: ");
    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;
}

This method uses the Sieve of Eratosthenes algorithm to efficiently find prime numbers up to the given input.

While it may be overkill for checking primality of a single number, it's useful when dealing with multiple numbers.

Conclusion

In this article, we explored different methods to check if a number is prime in the C programming language.

The brute-force approach is the most straightforward, but we can optimize it by skipping unnecessary iterations or employ more advanced algorithms like the Sieve of Eratosthenes for better performance.

The choice of method depends on the specific requirements of your application, and understanding these different approaches allows you to make informed decisions based on the context in which you are working.