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.

Practice

1. What does it mean for a number to be prime?

easy

A. It is divisible by 2.

B. It has exactly two distinct positive divisors: 1 and itself.

C. It is an even number.

D. It has more than two divisors.

Solution

1. Step 1: Understand the definition of prime number

   A prime number is a number greater than 1 that has no divisors other than 1 and itself.

2. Step 2: Compare options with definition

   Only It has exactly two distinct positive divisors: 1 and itself. correctly states this definition. Options B, C, and D are incorrect because they describe properties that do not define prime numbers.

3. Final Answer:

   It has exactly two distinct positive divisors: 1 and itself. -> Option B

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime numbers have only 1 and itself as divisors [OK]

Common Mistakes:

• Thinking all even numbers are prime
• Confusing prime with composite numbers
• Including 1 as a prime number

2. Which of the following C code snippets correctly checks if a number n is prime?

easy

A. for(int i = 1; i < n; i++) { if(n % i == 0) return 0; } return 1;

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

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

D. for(int i = 2; i < n/2; i++) { if(n % i == 0) return 1; } return 0;

Solution

1. Step 1: Analyze loop range for divisor checking

   To check if n is prime, we test divisors from 2 up to n-1. for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; uses i < n, which is correct.

2. Step 2: Check return values and conditions

   for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; returns 0 if a divisor is found, else returns 1 meaning prime. Other options have incorrect loop ranges or return values.

3. Final Answer:

   for(int i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; -> Option C

4. Quick Check:

   Loop from 2 to n-1 and return 0 if divisible [OK]

Hint: Check divisors from 2 to n-1 for prime [OK]

Common Mistakes:

• Checking divisibility by 1
• Looping up to n instead of n-1
• Returning wrong values on divisor found

3. What is the output of the following C code when n = 11?

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

printf("%d", isPrime(n));

medium

A. 1

B. Compilation error

C. 0

D. Infinite loop

Solution

1. Step 1: Analyze the for loop condition

   In C, relational operators (<, <=) associate left-to-right with same precedence. i < i * i <= n parses as (i < (i * i)) <= n. For i ≥ 2, i < i*i is true (1), so 1 <= n is true. Condition always true.

2. Step 2: Runtime behavior

   Loop never terminates (infinite loop). No printf output.

3. Final Answer:

   Infinite loop -> Option D

4. Quick Check:

   (i < i*i) <= n always true [OK]

Hint: C relational ops left-to-right: (i < i*i) <= n always true [OK]

Common Mistakes:

• Thinking chained comparisons cause compile error
• Assuming Python-like chained comparison
• Believing loop stops at sqrt(n)

4. Find the error in this C function to check if n is prime:

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

medium

A. Using assignment operator '=' instead of comparison '==' in if condition

B. Loop should run till i < n, not n / 2

C. Missing return statement at the end

D. No error, code is correct

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses n % i = 0 which is assignment, not comparison.

2. Step 2: Understand impact of assignment in condition

   This causes a syntax error or unintended behavior. It should be n % i == 0 to compare.

3. Final Answer:

   Using assignment operator '=' instead of comparison '==' in if condition -> Option A

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' to compare, '=' assigns value [OK]

Common Mistakes:

• Confusing '=' and '==' in conditions
• Looping till n/2 is actually correct optimization
• Ignoring compiler error messages

5. You want to optimize prime checking for large n. Which change improves efficiency the most?

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

hard

A. Change loop to run till i * i <= n instead of i <= n / 2

B. Check divisibility only by even numbers

C. Start loop from 1 instead of 2

D. Remove the initial check for n <= 1

Solution

1. Step 1: Understand loop optimization for prime checking

   Checking divisors up to n/2 is inefficient. We only need to check up to the square root of n.

2. Step 2: Apply loop condition using i * i <= n

   Changing the loop to run while i * i <= n reduces iterations and improves efficiency.

3. Final Answer:

   Change loop to run till i * i <= n instead of i <= n / 2 -> Option A

4. Quick Check:

   Check divisors up to sqrt(n) for efficiency [OK]

Hint: Check divisors only up to square root of n [OK]

Common Mistakes:

• Checking even numbers only misses odd divisors
• Starting loop from 1 wastes time
• Removing base case causes wrong results