C program to check if a number is prime number

Prime numbers play a significant role in various fields of mathematics and computer science. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This article will guide you through writing a C program to check if a given number is a prime number.

Introduction

Prime numbers are fundamental in number theory and have numerous applications in computer science, particularly in cryptography. Checking if a number is prime is a common task that can be efficiently performed using basic programming techniques.

Method to Check for Prime Numbers

To determine if a number n is prime, we can use the following method:

1. If n is less than or equal to 1, it is not a prime number.
2. If n is 2, it is a prime number.
3. If n is divisible by any number from 2 to √n, it is not a prime number.
4. If none of the above conditions are met, n is a prime number.

The rationale behind checking up to √n is that a larger factor of n would necessarily be paired with a smaller factor that has already been checked.

C Program to Check for Prime Numbers

Here is a C program that checks if a given number is a prime number:

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

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

    // Taking input from the user
    printf("Enter an integer: ");
    scanf("%d", &num);

    // Check if number is less than or equal to 1
    if (num <= 1) {
        isPrime = 0;
    } else {
        // Check for factors from 2 to sqrt(num)
        for (i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) {
                isPrime = 0;
                break;
            }
        }
    }

    // Displaying the result
    if (isPrime) {
        printf("%d is a prime number.", num);
    } else {
        printf("%d is not a prime number.", num);
    }

    return 0;
}

Output

Enter an integer: 5
5 is a prime number.

Explanation of the Code

1. Input: The program takes an integer input from the user.
2. Initial Check: It checks if the number is less than or equal to 1. If so, it sets isPrime to 0 (indicating not prime).
3. Prime Check Loop: For numbers greater than 1, the program uses a loop to check divisibility from 2 up to √n. If any number divides num evenly, it sets isPrime to 0 and breaks out of the loop.
4. Output: Based on the value of isPrime, the program prints whether the number is prime or not.

Why Check Up to √n?

Checking up to √n reduces the number of iterations significantly, especially for large numbers. For instance, to check if 29 is prime, instead of checking up to 28, we only need to check up to approximately 5 (since √29 ≈ 5.39). This optimization makes the algorithm much more efficient.