How to Determine Whether a Number is Prime in C Program

1. What is a Prime Number ?

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. In other words, a prime number is only divisible by 1 and itself. Here are a few key characteristics of prime numbers:

1. Divisibility: A prime number has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are prime numbers because they cannot be evenly divided by any other numbers.
2. Countability: There are infinitely many prime numbers. This was proven by the ancient Greek mathematician Euclid more than 2,000 years ago in a theorem known as Euclid’s theorem.
3. Role in Number Theory: Prime numbers play a fundamental role in number theory and have applications in various areas of mathematics and computer science, such as cryptography.
4. Primality Testing: Determining whether a given number is prime or composite is a classical problem in number theory. There are several algorithms and methods for primality testing, and it remains an active area of research.

Prime numbers have unique mathematical properties and are essential in many mathematical and computational contexts.

2. Determining Whether a Number is Prime in a C Program

To determine whether a number is prime in a C program, you can use the following approach. The idea is to check for divisors up to the square root of the number because any factors beyond the square root would have corresponding factors that were already checked.

Example 2.1 )  Determining whether a number is prime

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

// Function to check if a number is prime
bool isPrime(int num) {
    if (num <= 1) {
        return false;  // 1 and negative numbers are not prime
    }

    // Iterate from 2 up to the square root of num
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;  // num has a factor, it's not prime
        }
    }

    return true;  // No factors found, it's prime
}

int main() {
    int number;

    // Input the number to check
    printf("Enter a number: ");
    scanf("%d", &number);

    // Call the function to check if it's prime and output the result
    if (isPrime(number)) {
        printf("%d is a prime number.\n", number);
    } else {
        printf("%d is not a prime number.\n", number);
    }

    return 0;
}

Explanation:

1. The isPrime function takes an integer as a parameter and returns a boolean value indicating whether the number is prime.
2. In the main function, the user inputs a number, and then the program calls the isPrime function to check if it’s prime. The result is then printed.
3. The program checks for factors by iterating from 2 up to the square root of the input number. If a factor is found, the number is not prime.
4. The sqrt function from the math.h library is used to calculate the square root. Note that for performance reasons, some implementations might use i * i <= num instead of i <= sqrt(num).

Output

Enter a number: 17
17 is a prime number.

In this example, the user entered the number 17, and the program determined that 17 is a prime number. The output message reflects this result. If you input a different number, the output will change accordingly.