Why Check if Number is Prime in DSA C?

The Big Idea

What if you could skip most checks and still know if a number is prime instantly?

The Scenario

Imagine you want to find out if a number is prime by checking every number smaller than it one by one. For example, to check if 29 is prime, you try dividing it by 2, 3, 4, 5, and so on until 28.

The Problem

This manual method is very slow and tiring, especially for big numbers. It wastes time checking many unnecessary numbers and can easily lead to mistakes or missed checks.

The Solution

Using a simple rule, we only check divisors up to the square root of the number. This cuts down the work a lot and quickly tells us if the number is prime or not.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This method makes it easy and fast to check prime numbers even for very large values.

Real Life Example

Prime numbers are used in computer security to create keys that protect your online information.

Key Takeaways

Manual checking every number is slow and error-prone.

Checking only up to the square root speeds up the process.

This helps in fast prime number detection for many applications.

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