C Program to Check Prime Number Using Efficient Logic

 

Introduction

A prime number is a number that has exactly two distinct positive divisors: 1 and itself. In this program, we check whether a given number is prime or not using a simple and efficient logic. This type of program is commonly used in mathematics, competitive programming, and basic algorithm learning for beginners in C programming.

Problem Statement

The task is to write a C program that determines whether a given integer is a prime number or not. The program takes a single integer input from the user and analyzes its divisibility. If the number has no divisors other than 1 and itself, it should be identified as a prime number; otherwise, it is not prime. This problem is important in number theory and has practical relevance in areas such as cryptography, data validation, and algorithm design.

 Algorithm / Logic Explanation

To check whether a number is prime, we need to verify that it is not divisible by any number other than 1 and itself. The algorithm follows a simple and efficient approach.

Step-by-step logic:

• Read an integer number from the user.

• If the number is less than or equal to 1, it is not a prime number.

• Start checking divisibility from 2 up to the square root of the number.

• If the number is divisible by any value in this range, it is not prime.

• If no divisor is found, the number is prime.

Why this works: Any composite number must have at least one factor less than or equal to its square root. By limiting the loop to this range, unnecessary iterations are avoided, making the algorithm more efficient.

Pseudocode:

• Input number

• If number ≤ 1 → Not Prime

• For i = 2 to i × i ≤ number

  • If number mod i = 0 → Not Prime

• Otherwise → Prime

Code

#include <stdio.h>

int main()
{
    int num;
    printf("Enter the number:\n");
    scanf("%d", &num);

    if (num <= 1)
    {
        printf("%d is not a prime number.\n", num);
        return 0;
    }

    for (int i = 2; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            printf("%d is not a prime number.\n", num);
            return 0;
        }
    }

    printf("%d is a prime number.\n", num);
    return 0;
}

Sample Input / Output

Sample Input: 7
Sample Output: 7 is a prime number.

Sample Input: 10
Sample Output: 10 is not a prime number.

 Explanation of Code

The program begins by including the standard input-output header file, which allows the use of functions like printf and scanf. Inside the main function, an integer variable num is declared to store the number entered by the user. The program prompts the user for input and reads the value using scanf.

The first if condition checks whether the entered number is less than or equal to 1. This step is important because numbers such as 0, 1, and negative values are not considered prime by definition. If this condition is true, the program immediately prints the result and terminates, saving unnecessary computation.

Next, a for loop is used to test whether the number has any divisors other than 1 and itself. The loop starts from 2 and runs while i * i is less than or equal to the given number. This condition effectively limits the checks up to the square root of the number, which significantly improves efficiency compared to checking all values up to the number itself.

Inside the loop, the modulus operator (%) checks if the number is divisible by the current value of i. If a divisor is found, the program prints that the number is not prime and exits immediately. If the loop completes without finding any divisors, the final printf statement confirms that the number is prime. This approach uses minimal memory and ensures fast execution, even for larger input values.

Edge Cases / Notes

• Numbers less than or equal to 1 are not considered prime and are handled separately.

• The program works efficiently even for large numbers due to the square root optimization.

• Only integer input is supported; decimal values are not applicable for prime checking.

• The algorithm uses constant extra memory, making it suitable for systems with limited resources.

Conclusion

In this program, we implemented an efficient method to check whether a given number is prime using C programming. By reducing unnecessary iterations and handling edge cases properly, the solution remains fast and reliable. This logic is widely used in mathematics, cryptography, and algorithm design.

FAQs

Q1. What is a prime number?
A prime number is a natural number greater than 1 that has exactly two distinct divisors: 1 and itself. Examples include 2, 3, 5, and 7.

Q2. Why do we check divisibility only up to the square root of a number?
If a number has a divisor greater than its square root, it must also have a corresponding divisor smaller than the square root. Therefore, checking up to this limit is sufficient and improves efficiency.

Q3. Can this program be written using recursion?
Yes, prime number checking can be implemented using recursion, but iterative solutions are generally simpler and more efficient in terms of memory usage.

Q4. Is this program suitable for very large numbers?
The logic works well for moderately large integers, but for extremely large numbers, advanced algorithms like probabilistic primality tests are preferred.

Keywords 

C program to check prime number, prime number program in C, C language prime number example, check prime number in C, prime number logic in C, basic C programs, C programming for beginners, number theory in C, efficient prime checking algorithm

Hashtags

#cprogramming #clanguage #coding #programming #1printf #algorithms #numbertheory #beginners

 Related Posts

• Related: C Program to Check Prime Number Using Functions

• Related: C Program to Find Prime Numbers Between Two Intervals

• Related: C Program for Palindrome Number

Similar Search

prime number program in c, how to check prime number in c, c program for prime number using loop, efficient prime number algorithm in c