Check if Number is Prime in DSA C - Build from Scratch

Check if Number is Prime

📖 Scenario: You are helping a friend who wants to know if a number is prime. A prime number is a number greater than 1 that has no divisors other than 1 and itself.We will write a simple program in C to check if a given number is prime.

🎯 Goal: Build a C program that checks if a number is prime by testing divisibility from 2 up to the number minus one.

📋 What You'll Learn

Create an integer variable called number with the value 29

Create an integer variable called is_prime and set it to 1 (true)

Use a for loop with variable i from 2 to number - 1

Inside the loop, check if number is divisible by i

If divisible, set is_prime to 0 (false) and break the loop

Print "Prime" if is_prime is 1, otherwise print "Not Prime"

💡 Why This Matters

🌍 Real World

Prime numbers are used in cryptography, computer security, and coding theory.

💼 Career

Understanding prime checking helps in algorithm design and problem solving in software development.

1

Create the number variable

Create an integer variable called number and set it to 29.

DSA C

#include 

int main() {
    // Create an integer variable called number and set it to 29
    
    return 0;
}

Hint

Use int number = 29; inside main().

2

Create the is_prime variable

Create an integer variable called is_prime and set it to 1 inside main() after number.

DSA C

#include 

int main() {
    int number = 29;
    // Create an integer variable called is_prime and set it to 1
    
    return 0;
}

Hint

Use int is_prime = 1; to assume the number is prime initially.

3

Check divisibility with a for loop

Use a for loop with variable i from 2 to number - 1. Inside the loop, check if number % i == 0. If yes, set is_prime to 0 and break the loop.

DSA C

#include 

int main() {
    int number = 29;
    int is_prime = 1;
    // Use a for loop from i = 2 to number - 1
    // Check if number is divisible by i
    // If divisible, set is_prime to 0 and break
    
    return 0;
}

Hint

Use for (int i = 2; i < number; i++) and inside check if (number % i == 0).

4

Print if the number is prime or not

Use an if statement to print "Prime" if is_prime is 1, otherwise print "Not Prime".

DSA C

#include 

int main() {
    int number = 29;
    int is_prime = 1;

    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            is_prime = 0;
            break;
        }
    }

    // Print "Prime" if is_prime is 1, else print "Not Prime"
    
    return 0;
}

Hint

Use if (is_prime == 1) and printf("Prime\n"), else print "Not Prime".

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