A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This means that a prime number can only be divided evenly by 1 and the number itself without leaving a remainder.

Logic to Check for Prime Numbers:

1. Input a number $n$ from the user.
2. Check if $n$ is less than or equal to 1. If so, it is not prime.
3. For numbers greater than 1, check for factors from 2 up to the square root of $n$. If $n$ is divisible by any of these numbers, it is not prime.
4. If no divisors are found, $n$ is prime.

Program:

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

#include <stdio.h>
#include <math.h> // Include math library for sqrt function

int main() {
    int n, i, isPrime = 1; // Assume number is prime until proven otherwise

    // Input a positive integer from the user
    printf("Enter a positive integer: ");
    scanf("%d", &n);

    // Check for invalid input
    if (n <= 1) {
        printf("%d is not a prime number.\n", n);
        return 0; // Exit the program
    }

    // Check for factors
    for (i = 2; i <= sqrt(n); i++) { // Check up to the square root of n
        if (n % i == 0) {
            isPrime = 0; // Number is not prime
            break; // Exit the loop if a factor is found
        }
    }

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

    return 0;
}

Explanation:

1. Variables:

   • int n: Holds the integer input by the user.
   • int i: Loop variable for checking divisors.
   • int isPrime: A flag initialized to 1 (true), assuming the number is prime.

2. Input:

   • The user is prompted to enter a positive integer.

3. Invalid Input Check:

   • If $n$ is less than or equal to 1, the program states that it is not a prime number and exits.

4. Loop for Checking Factors:

   • The program loops from 2 to the square root of $n$ (inclusive) to check for divisors.
   • If $n$ is divisible by any $i$, isPrime is set to 0 (false), and the loop breaks.

5. Output:

   • After checking, the program prints whether $n$ is a prime number or not based on the value of isPrime.

Sample Output:

Example 1:

Enter a positive integer: 7
7 is a prime number.

Example 2:

Enter a positive integer: 10
10 is not a prime number.

Key Points:

• Efficiency: The program only checks divisibility up to the square root of $n$, which significantly reduces the number of iterations for larger numbers compared to checking up to $n-1$.
• Input Validation: The program checks for numbers less than or equal to 1 to avoid unnecessary calculations.
• Output Clarity: Clear messaging is provided to the user based on whether the number is prime or not.