🚀⚡Beginner

Check Whether a Number is Prime

Determine if a number is prime

A prime number is a natural number greater than 1 and is completely divisible only by 1 and itself. In this example, we will learn how to check whether a given number is prime or not using different approaches.

📝 Examples

Input: n = 29

Output: 29 is Prime

Explanation: 29 has no divisors other than 1 and 29 itself. Hence, it is a prime number.

Input: n = 15

Output: 15 is NOT Prime

Explanation: 15 has divisors other than 1 and 15 (i.e., 3 and 5). Hence, it is not prime.

📋 Approaches Covered

Brute Force Method - O(n) Time
Optimized Approach - O(√n) Time
Further Optimized - Skip Even Numbers

1. Brute Force Method - O(n) Time

We check whether the number is prime by iterating from 1 to n using loops. We count the number of divisors. If there are more than 2 divisors (including 1 and n), then n is not prime. This is called the trial division method.

prime_brute_force.c

1#include <stdbool.h>
2#include <stdio.h>
3
4int main() {
5    int n = 29;
6    int cnt = 0;
7
8    // If number is less than/equal to 1,
9    // it is not prime
10    if (n <= 1)
11        printf("%d is NOT prime", n);
12    else {
13
14        // Count all divisors of given number
15        for (int i = 1; i <= n; i++) {
16
17            // Check n is divided by i or not
18            if (n % i == 0)
19                cnt++;
20        }
21
22        // If n is divisible by more than 2 numbers
23        // then it is not prime
24        if (cnt > 2)
25            printf("%d is NOT prime", n);
26
27        // else it is prime
28        else
29            printf("%d is prime", n);
30    }
31    return 0;
32}

Output

29 is prime

⏱️ Time Complexity: O(n) - We iterate from 1 to n

2. Optimized Approach - O(√n) Time

To optimize the above approach, we use a mathematical property:

"The smallest factor of a number greater than one cannot be greater than the square root of that number."

Using this, we can reduce the numbers to be checked from N to √N, making it much more efficient.

prime_optimized.c

1#include <math.h>
2#include <stdbool.h>
3#include <stdio.h>
4
5int main() {
6    int n = 29;
7    int cnt = 0;
8
9    // If number is less than/equal to 1,
10    // it is not prime
11    if (n <= 1)
12        printf("%d is NOT prime", n);
13    else {
14
15        // Check how many numbers divide n in
16        // range 2 to sqrt(n)
17        for (int i = 2; i * i <= n; i++) {
18            if (n % i == 0)
19                cnt++;
20        }
21
22        // if cnt is greater than 0 then n is
23        // not prime
24        if (cnt > 0)
25            printf("%d is NOT prime", n);
26
27        // else n is prime
28        else
29            printf("%d is prime", n);
30    }
31    return 0;
32}

Output

29 is prime

⏱️ Time Complexity: O(√n) - We iterate only √n times

3. Further Optimized - Skip Even Numbers

We can further optimize by skipping all even numbers greater than 2. Since the only even prime number is 2, we can skip all even numbers between 3 and √n.

prime_skip_even.c

1#include <math.h>
2#include <stdbool.h>
3#include <stdio.h>
4
5int main() {
6    int n = 29;
7    int cnt = 0;
8
9    // If number is <= 1 or even (except 2)
10    // then it is not prime
11    if (n <= 1 || ((n > 2) && (n % 2 == 0)))
12        printf("%d is NOT prime", n);
13    else {
14        if (n == 2) {
15            printf("%d is prime", n);
16            return 0;
17        } else {
18            // Check only odd numbers from 3 to sqrt(n)
19            for (int i = 3; i * i <= n; i += 2) {
20                if (n % i == 0)
21                    cnt++;
22            }
23
24            // if cnt is greater than 0 then n is
25            // not prime
26            if (cnt > 0)
27                printf("%d is NOT prime", n);
28
29            // else n is prime
30            else
31                printf("%d is prime", n);
32        }
33    }
34
35    return 0;
36}

Output

29 is prime

📖 Code Explanation

Code	Explanation
n <= 1	Numbers ≤ 1 are not prime by definition
i * i <= n	Check up to √n (equivalent to i <= sqrt(n))
n % i == 0	If n is divisible by i, it's not prime
i += 2	Skip even numbers (check only 3, 5, 7, 9...)
cnt > 0	If any divisor found, number is not prime