Construct a C program to check if entered integer is a prime number or not

Notes:
To construct a C program that checks whether a given integer is a prime number or not, follow
the steps outlined below. We will use a simple method where we check if the number is divisible
by any number from 2 to the square root of the given number.

Step-by-Step Explanation:

1. Understand the Concept of Prime Numbers:
● A prime number is a number greater than 1 that has no divisors other than 1
and itself. For example, numbers like 2, 3, 5, 7, and 11 are prime numbers.
● A composite number, on the other hand, is a number that has divisors other
than 1 and itself. For example, 4, 6, 8, and 9 are composite numbers.

2. Input from User:
● We first need to take an integer input from the user. This will be the number we
need to check for primality.

3. Initial Check for Edge Cases:
● If the input number is less than or equal to 1, we can directly conclude that the
number is not prime because prime numbers are greater than 1.

4. Prime Check Logic:
● For numbers greater than 1, we need to check if they are divisible by any number
between 2 and the square root of the number. The reason we only check up to
the square root is based on the fact that if a number is divisible by a larger
number, it must also be divisible by a smaller number. For example, if 36 is
divisible by 6, it must also be divisible by 2, since 36 ÷ 6 = 6.

5. Algorithm:
● Start by assuming that the number is prime.
● Check divisibility using a for loop from 2 to the square root of the number.
● If any divisor is found, the number is not prime.
● If no divisor is found, the number is prime.

C Program Code:

#include <stdio.h>
#include <math.h>
// Function to check if a number is prime
int isPrime(int num) {
if (num <= 1) {
return 0; // Not prime
}
// Check for divisibility from 2 to sqrt(num)
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return 0; // Not prime
}
}
return 1; // Prime
}
int main() {
int num;
// Take input from the user
printf("Enter an integer: ");
scanf("%d", &num);
// Check if the number is prime
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:
1. Header Files:
● We include stdio.h for input/output functions and math.h for the sqrt()
function, which helps us calculate the square root of a number.

2. isPrime Function:
● This function checks if the given number num is prime.
● If num <= 1, we return 0, indicating that the number is not prime.
● We then loop from 2 to the square root of num using the sqrt() function. If num
is divisible by any number in this range, we return 0, meaning the number is not
prime.
● If no divisors are found, we return 1, indicating that the number is prime.

3. main Function:
● In the main function, we prompt the user to input a number.
● We call the isPrime function to check whether the number is prime.
● The result is then printed to the screen.

Example Walkthrough:

Example 1:
● Input: 7
● The isPrime function checks divisibility from 2 to √7 (approximately 2.65), so only
numbers 2 can divide 7.
● 7 is not divisible by 2, so it is a prime number.
● Output: "7 is a prime number."

Example 2:
● Input: 10
● The isPrime function checks divisibility from 2 to √10 (approximately 3.16), so we
check divisibility by 2 and 3.
● 10 is divisible by 2, so it is not a prime number.
● Output: "10 is not a prime number."
Time Complexity:
● The time complexity of this algorithm is O(√n), where n is the number being checked.
This is because we only need to check divisibility up to the square root of the number.