Check if Number is Prime in DSA C

Mental Model

A prime number is only divisible by 1 and itself. To check if a number is prime, we try dividing it by smaller numbers to see if any divide evenly.

Analogy: Imagine you have a box of candies and you want to split them evenly among friends. If you can only split them evenly with 1 friend or all friends together, the number of candies is prime.

Number: 7
Try dividing by: 2, 3, 4, 5, 6
If none divide evenly -> prime

7
↑ Check divisors -> 2, 3, 4, 5, 6

Dry Run Walkthrough

Input: Check if number 7 is prime

Goal: Determine if 7 has any divisors other than 1 and itself

Step 1: Check if 7 is less than 2 (not prime if yes)

7 (number to check)

Why: Numbers less than 2 are not prime

Step 2: Try dividing 7 by 2

7 % 2 = 1 (not divisible)

Why: If divisible, 7 is not prime

Step 3: Try dividing 7 by 3

7 % 3 = 1 (not divisible)

Why: Continue checking divisors up to sqrt(7)

Step 4: No divisors found up to sqrt(7), conclude 7 is prime

7 is prime

Why: No number between 2 and sqrt(7) divides 7 evenly

Result:

7 is prime

Annotated Code

DSA C

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

int isPrime(int n) {
    if (n < 2) {
        return 0; // Numbers less than 2 are not prime
    }
    int limit = (int)sqrt(n);
    for (int i = 2; i <= limit; i++) {
        if (n % i == 0) {
            return 0; // Found a divisor, not prime
        }
    }
    return 1; // No divisors found, prime
}

int main() {
    int number = 7;
    if (isPrime(number)) {
        printf("%d is prime\n", number);
    } else {
        printf("%d is not prime\n", number);
    }
    return 0;
}

if (n < 2) { return 0; }

Exclude numbers less than 2 as they are not prime

int limit = (int)sqrt(n);

Only check divisors up to square root of n to reduce work

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

Check each number from 2 to limit; if divides evenly, n is not prime

return 1;

If no divisors found, n is prime

Output

7 is prime

Complexity Analysis

Time: O(√n) because we only check divisors up to the square root of n

Space: O(1) because we use a fixed amount of extra space regardless of input size

vs Alternative: Naive approach checks all numbers up to n-1 (O(n)), this method is faster by limiting checks to √n

Edge Cases

number less than 2 (e.g., 0 or 1)

Function returns not prime immediately

DSA C

if (n < 2) { return 0; }

number is 2 (smallest prime)

Function returns prime since no divisors between 2 and sqrt(2)

DSA C

for (int i = 2; i <= limit; i++) { ... }

number is a perfect square (e.g., 9)

Function detects divisor at sqrt(n) and returns not prime

DSA C

if (n % i == 0) { return 0; }

When to Use This Pattern

When you need to check if a number is prime, use the divisor check up to square root pattern because it efficiently finds factors without unnecessary checks.

Common Mistakes

Mistake: Checking divisors up to n-1 instead of sqrt(n), causing slow performance
Fix: Limit divisor checks to numbers up to the square root of n

Mistake: Not handling numbers less than 2 correctly, marking them as prime
Fix: Add a condition to return not prime for numbers less than 2

Summary

Checks if a number is prime by testing divisibility up to its square root.

Use when you need to quickly determine if a number has any divisors other than 1 and itself.

Only check divisors up to the square root because any larger divisor would have a smaller paired divisor already checked.