C Program to Check Prime Number

In C programming, checking whether a number is prime is a fundamental task often covered in C tutorials. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This article explains the concept of prime numbers and demonstrates how to write a C program to check if a given number is prime.

What is a Prime Number?

A number is considered a prime number if it meets the following conditions:

• It is greater than 1.
• It has only two factors: 1 and itself.

For example:

• Prime numbers: 2, 3, 5, 7, 11, 13, 17
• Non-prime numbers: 4 (divisible by 2), 6 (divisible by 2 and 3), 8 (divisible by 2)

Steps to Check Prime Number in C

The process of determining whether a number is prime involves the following steps:

1. Input the number to be checked.
2. Verify if the number is less than or equal to 1 (not prime).
3. Iterate from 2 to the square root of the number and check divisibility.
4. If divisible by any number in the range, it's not prime; otherwise, it is.

C Program to Check Prime Number

Here’s a simple C program to check if a number is prime:

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

int main() {
    int num, i, isPrime = 1;
    
    printf("Enter a number: ");
    scanf("%d", &num);

    if (num <= 1) {
        isPrime = 0; // Numbers <= 1 are not prime
    } else {
        for (i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) {
                isPrime = 0; // Not a prime number
                break;
            }
        }
    }

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

    return 0;
}

Explanation of the Code

1. Input: The user enters a number.
2. Check for non-prime cases: Numbers less than or equal to 1 are immediately flagged as non-prime.
3. Iterate: The loop checks divisibility from 2 to the square root of the number for efficiency.
4. Output: Based on divisibility, the program outputs whether the number is prime or not.

Optimized Approach for Checking Prime Numbers

The above method can be further optimized:

• Directly return false for even numbers greater than 2.
• Use an optimized loop that checks divisibility by 2 and 3 first, and then tests numbers in the form
  📄
  6k ± 1.

Example of Optimized Code

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

Common FAQs About Prime Numbers in C

What is the significance of prime numbers in programming?

Prime numbers are essential in cryptography, hashing functions, and various algorithms in computer science.

Why do we iterate up to the square root of the number?

Divisors of a number appear in pairs. If a number has a divisor greater than its square root, the corresponding pair divisor must be smaller than the square root. Thus, iterating up to the square root improves efficiency.

Can 1 be considered a prime number?

No, 1 is not a prime number because it only has one factor: itself.

What is the difference between a prime number and a composite number?

A prime number has exactly two factors (1 and itself), whereas a composite number has more than two factors.

Conclusion

Understanding how to check for a prime number in C programming is a fundamental skill for programmers. By implementing efficient algorithms and optimizing code, you can perform number-checking operations swiftly and accurately. Explore more C tutorials to enhance your coding expertise.