C Program to Check Prime Number with Output and Explanation

A C program to check a prime number uses a loop to test if the number is divisible by any number from 2 to its square root; if no divisor is found, it is prime. For example, use for (int i = 2; i * i <= n; i++) and check if (n % i == 0) to decide.

Examples

Input7

Output7 is a prime number.

Input10

Output10 is not a prime number.

Input1

Output1 is not a prime number.

How to Think About It

To check if a number is prime, think about whether it can be divided evenly by any number other than 1 and itself. Start checking from 2 up to the square root of the number because if it has a factor larger than its square root, it must have a smaller one too. If you find any number that divides it evenly, it is not prime; otherwise, it is prime.

Algorithm

1

Get the input number.

2

If the number is less than 2, it is not prime.

3

Check divisibility from 2 up to the square root of the number.

4

If any divisor divides the number evenly, mark it as not prime.

5

If no divisors are found, mark the number as prime.

6

Print the result.

Code

c

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

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

    if (n < 2) {
        isPrime = 0;
    } else {
        for (i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                isPrime = 0;
                break;
            }
        }
    }

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

    return 0;
}

Output

Enter a number: 7
7 is a prime number.

Dry Run

Let's trace the input 7 through the code to see how it checks for prime.

1

Input number

User enters n = 7

2

Check if less than 2

7 is not less than 2, continue

3

Loop from 2 to sqrt(7)

sqrt(7) ≈ 2.64, so i goes from 2 to 2

4

Check divisibility

7 % 2 != 0, so no divisor found

5

No divisors found

isPrime remains 1, number is prime

6

Print result

Print '7 is a prime number.'

i	n % i	isPrime
2	1	1

Why This Works

Step 1: Start with input

We first get the number from the user to check if it is prime.

Step 2: Exclude numbers less than 2

Numbers less than 2 are not prime by definition, so we mark them immediately.

Step 3: Check divisors up to square root

We only check divisors up to the square root because any factor larger than that would have a matching smaller factor.

Step 4: Decide prime or not

If any divisor divides the number evenly, it is not prime; otherwise, it is prime.

Alternative Approaches

Check divisibility up to n-1

c

#include <stdio.h>

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

    if (n < 2) isPrime = 0;
    else {
        for (i = 2; i < n; i++) {
            if (n % i == 0) {
                isPrime = 0;
                break;
            }
        }
    }

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

    return 0;
}

This method is simpler but slower because it checks all numbers up to n-1 instead of up to the square root.

Use a function to check primality

c

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

int isPrime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

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

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

    return 0;
}

Using a function improves code reuse and readability, especially for larger programs.

Complexity: O(√n) time, O(1) space

Time Complexity

The loop runs up to the square root of n, so the time grows roughly with √n.

Space Complexity

Only a few variables are used, so space is constant O(1).

Which Approach is Fastest?

Checking up to the square root is faster than checking up to n-1, and using a function helps organize code but does not affect complexity.

Approach	Time	Space	Best For
Check up to sqrt(n)	O(√n)	O(1)	Efficient primality test
Check up to n-1	O(n)	O(1)	Simple but slower
Function-based check	O(√n)	O(1)	Reusable and clean code