C Program to Check Whether a Number is Prime or Not

Checking if a number is prime is pretty common in programming. A prime number’s only divisible by 1 and itself. Like, take the number 17; it’s prime since it has no divisors other than 1 and 17.

In this article, we’re gonna write a C program to check if an entered number is prime. So, let’s dive in!

Prerequisites for the C Program to Check Prime Number

Before you dive into the code, make sure you're familiar with these prerequisites.

• Basic understanding of conditional statements and loops in C
• Using the modulo % operator to find remainders
• Any C compiler such as GCC 9 or newer — or just run it in the EduSeekho online compiler

Source Code of C Program to Check Whether a Number is Prime or Not

Here's the complete C code to check if a number is prime.

#include <stdio.h>

int main() {
    int n, i, isPrime = 1;
    // Read number from user
    printf("Enter a number: ");
    scanf("%d", &n);

    // Check if n is less than or equal to 1
    if (n <= 1) {
        isPrime = 0;
    } else {
        // Check for factors from 2 to n/2
        for (i = 2; i <= n / 2; i++) {
            // If n is divisible by any i
            if (n % i == 0) {
                isPrime = 0;
                break;
            }
        }
    }

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

    return 0;
}

Output of the Check Whether a Number is Prime Program

Let's see the result when you run this program.

Enter a number: 17
17 is a prime number.

Algorithm to Check Whether a Number is Prime in C

Checking if a number is prime involves testing its divisibility. Here's how this program accomplishes the task, step by step.

1. Read the integer n from the user.
2. Initialize isPrime to 1, assuming the number is prime.
3. If n is less than or equal to 1, set isPrime to 0.
4. For each i from 2 to n/2:
5.   If n is divisible by i, set isPrime to 0 and break the loop.
6. Output the result based on the value of isPrime.

flowchart TD
  A([Start]) --> B[/Input n/]
  B --> C[isPrime = 1]
  C --> D[/If n <= 1/]
  D -->|Yes| E[isPrime = 0]
  E --> I["Output isPrime"]
  D -->|No| F["for (i = 2; i <= n/2; i++)"]
  F --> G{"n %% i == 0?"}
  G -->|Yes| H[isPrime = 0]
  H --> I
  G -->|No| F
  I --> J([End])

How the C Program to Check Prime Number Works

Here’s a detailed breakdown of how the code works, line by line.

• #include <stdio.h>: Includes the standard input-output library, needed for printf and scanf.
• int main(): The main function where the execution begins.
• int n, i, isPrime = 1;: Declares integer variables n and i, and initializes isPrime to 1, assuming n is prime until proven otherwise.
• scanf("%d", &n);: Reads an integer from the user and stores it in n.
• if (n <= 1): Checks if n is less than or equal to 1; if so, it's not prime.
• The else clause handles numbers greater than 1 to check for factors.
• for (i = 2; i <= n / 2; i++): Loops from 2 to n/2 to check for factors.
• if (n % i == 0): If n is divisible by i, it's not prime, and isPrime is set to 0.
• printf("%d is a prime number.\n", n);: If isPrime remains 1, output that n is prime.
• printf("%d is not a prime number.\n", n);: Otherwise, output that n is not prime.
• return 0;: Ends the main function, returning 0 to indicate successful execution.

How Fast Is the Check Prime Number Program in C?

Understanding the time and space complexity of this program helps optimize performance.

Time Complexity: O(n/2) where n is the entered number. The loop runs up to n/2 iterations, making it perform about 10 checks for n = 20.

Space Complexity: O(1). Only n, i, and isPrime are used — three ints, regardless of the input size.

Key takeaway:Getting the hang of primality tests is key in number theory and algorithm tweaks.

FAQs About Checking if a Number is Prime in C

Here are answers to some common questions about this program.

Related Programs

If you found this program helpful, check out these related programs:

• C Program to Display Factors of a Number
• C Program to Check Prime or Armstrong Number Using User-defined Function
• C Program to Check if a Number is Sum of Two Primes
• C Program to Check Armstrong Number
• C Program to Display Armstrong Number Between Two Intervals

Conclusion

With this program, you can easily check if a number is prime. Next, give writing a program to find all prime numbers in a range a shot. It builds on this logic and helps with more advanced number theory problems.

Test your skills with our C quiz or try running the code again in the online compiler.