Prime Numbers in C

Prime Numbers in C: A Comprehensive Guide

by

Prime Numbers in C: A Comprehensive Guide || Find a prime number in c || Check prime number in C

The concept of prime numbers forms a fundamental underpinning in mathematics and both within a subset of number theory. Prime numbers involve solving tasks (primality testing, prime number generation) that can be more or less complex. In this article, we are going to see How To Find Prime Numbers In C programming language

What is a Prime Number?

A prime number is a natural number with no divisors other than 1 and itself, Put simply, for a number to be prime it should only be divisible by 1 and the number itself. For instance, 2, 3, 5, and 7 are prime numbers.

Prime Number Algorithm in C

Ultimately, we need an efficient algorithm to determine if a number is prime. The most common method is to check the divisibility until the square root of a number.

Check Prime Number in Cconduct}while( number <= 1 ); //This will make calling the check_prime() smoother rather than only providing warnings that are not so informative in case of an unwanted value.

Simple C Program to Find a prime number in c

To explain this in really simple terms, here is a program to find whether a given number is prime or not:

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

int isPrime(int n) {
    if (n <= 1) return 0; // Numbers less than or equal to 1 are not prime
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0; // If divisible by any number, not prime
    }
    return 1; // If no divisors are found, the number is prime
}

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;
}

Explanation of the Code

This function checks for divisibility up to the square root of the number to determine if a number is a prime or not.

  • Square Root Optimization: We do not have to check all numbers up to n, but we need only test from 2 up to sqrt(n), hence the amount of printed prime is min(p, (l-sqrt(r)) + 1).
  • Edge cases: Numbers less than or equal to 1 are handled before, as they are not prime.

Prime Number Generation in C >> Check prime number in C

In case you want to generate prime numbers within a range, then convert the algorithm to output all prime numbers till a certain limit.

A Few Prime Numbers (less than) for a given Limit

A program printing prime numbers till a number is given:

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

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

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

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

    return 0;
}

Optimizing Prime Number Calculations

The only thing to look out for is that checking every divisor if we are dealing with very large numbers, becomes extremely slow. Some common optimizations include:

  • Sieve of Eratosthenes: This generates all primes up to a given limit by marking the multiples of each prime, starting from 2.
  • No need to Check Even Numbers: After checking whether the number is perfectly divisible by 2, you could skip even numbers and just check odd divisors.

Sieve of Eratosthenes in C

The following C program to calculate all primes through N using the Sieve of Eratosthenes can be used as a primer.

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

void sieveOfEratosthenes(int limit) {
    bool primes[limit + 1];
    for (int i = 0; i <= limit; i++) {
        primes[i] = true;
    }

    for (int p = 2; p * p <= limit; p++) {
        if (primes[p] == true) {
            for (int i = p * p; i <= limit; i += p) {
                primes[i] = false;
            }
        }
    }

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

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

    sieveOfEratosthenes(limit);

    return 0;
}

Conclusion

Primes are one of the core concepts in math and thus programming. By using efficient algorithms such as the square root method/tools like the Sieve of Eratosthenes, you can easily check if a number is prime or get a list of prime numbers. You can include prime number calculation in your projects with ease C programming examples.

How to Find a Leap Year Using C?

Leave a Comment