Check if Number is Prime in DSA C - Time & Space Complexity

Time Complexity: Check if Number is Prime

O(√n)

Understanding Time Complexity

We want to know how the time to check if a number is prime grows as the number gets bigger.

How many steps does it take to decide if a number has no divisors other than 1 and itself?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= (int)sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}
    

This code checks if a number is prime by testing divisors from 2 up to the square root of the number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that tests divisors from 2 to sqrt(n).
• How many times: Approximately sqrt(n) times in the worst case.

How Execution Grows With Input

As the number n grows, the number of divisor checks grows roughly with the square root of n.

Input Size (n)	Approx. Operations
10	About 3 checks (2,3)
100	About 10 checks (2 to 10)
1000	About 31 checks (2 to 31)

Pattern observation: The number of steps grows slower than n, closer to the square root of n.

Final Time Complexity

Time Complexity: O(√n)

This means the time to check if a number is prime grows roughly with the square root of the number.

Common Mistake

[X] Wrong: "We must check all numbers from 2 up to n-1 to find if n is prime."

[OK] Correct: Checking beyond the square root is unnecessary because any larger factor pairs with a smaller one already checked.

Interview Connect

Understanding this time complexity helps you explain efficient prime checks and shows you can optimize simple loops, a useful skill in many coding problems.

Self-Check

"What if we checked divisors only up to n/2 instead of sqrt(n)? How would the time complexity change?"