Prime numbers play a crucial role in various fields, including cryptography, computer science, and mathematics. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This article will explore three distinct methods to write a prime number program in C programming language.

Explore three ways to write “Prime number program in C”

Method 1) Prime number program in C using Simple Iterative Approach

The simplest way to check if a number is prime is by dividing it by every number less than itself and greater than 1. If it is divisible by any of these numbers, it is not a prime number. Otherwise, it is prime.

Code Example

#include <stdio.h>

int isPrime(int num) {
    if (num <= 1) return 0; // 0 and 1 are not prime numbers
    for (int i = 2; i < num; i++) {
        if (num % i == 0) return 0; // If divisible by any number other than 1 and itself
    }
    return 1; // If not divisible by any number, it is prime
}

int main() {
    int number;
    printf("Enter a number: ");
    scanf("%d", &number);

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

    return 0;
}

Explanation of the Code

• The function isPrime takes an integer num as input.
• If num is less than or equal to 1, it returns 0 because 0 and 1 are not prime numbers.
• The function iterates from 2 to num-1 and checks if num is divisible by any of these numbers. If it finds any such number, it returns 0, indicating that num is not prime.
• If no divisors are found, the function returns 1, indicating that num is prime.

Method 2) Prime number program in C using Optimized Iterative Approach

Optimize the simple iterative approach by reducing the number of checks. You only need to check for divisors up to the square root of the number because a larger factor must be a multiple of a smaller factor that you have already checked.

Code Example

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

int isPrime(int num) {
    if (num <= 1) return 0; // 0 and 1 are not prime numbers
    if (num <= 3) return 1; // 2 and 3 are prime numbers
    if (num % 2 == 0 || num % 3 == 0) return 0; // Check if divisible by 2 or 3

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

int main() {
    int number;
    printf("Enter a number: ");
    scanf("%d", &number);

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

    return 0;
}

Explanation of the Code

• The function isPrime first handles the cases where num is less than or equal to 3.
• It then checks if num is divisible by 2 or 3.
• The loop starts from 5 and increments by 6, checking if num is divisible by i or i + 2. This skips even numbers and multiples of 3, reducing the number of iterations.
• The loop runs up to the square root of num, making it more efficient.

Method 3) Prime number program in C using Sieve of Eratosthenes

The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime number starting from 2.

Code Example

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

void sieveOfEratosthenes(int limit) {
    int *isPrime = (int *)malloc((limit + 1) * sizeof(int));
    memset(isPrime, 1, (limit + 1) * sizeof(int)); // Initialize array with 1s

    isPrime[0] = isPrime[1] = 0; // 0 and 1 are not prime numbers

    for (int p = 2; p * p <= limit; p++) {
        if (isPrime[p] == 1) {
            for (int i = p * p; i <= limit; i += p) {
                isPrime[i] = 0; // Mark multiples of p as non-prime
            }
        }
    }

    printf("Prime numbers up to %d are: ", limit);
    for (int p = 2; p <= limit; p++) {
        if (isPrime[p] == 1)
            printf("%d ", p);
    }
    printf("\n");

    free(isPrime); // Free the allocated memory
}

int main() {
    int limit;
    printf("Enter the limit: ");
    scanf("%d", &limit);

    sieveOfEratosthenes(limit);

    return 0;
}

Explanation of the Code

• The function sieveOfEratosthenes initializes an array isPrime with 1s, indicating all numbers are initially assumed to be prime.
• It marks 0 and 1 as non-prime.
• It iterates from 2 to the square root of the limit. For each prime number p, it marks its multiples as non-prime.
• Finally, it prints all the prime numbers up to the given limit.
• The use of dynamic memory allocation and initialization makes this method efficient for finding all primes up to a large number.

Finding prime numbers can be approached in various ways, each with its advantages and use cases. The simple iterative approach is easy to understand but inefficient for large numbers. The optimized iterative approach reduces the number of checks, making it faster. The Sieve of Eratosthenes is the most efficient for finding all primes up to a given limit but requires additional memory. By understanding these methods, programmers can choose the most suitable approach for their specific needs.