Check if Number is Prime in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of prime check for number 29

What is the output of this code when checking if 29 is prime?

DSA Python

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

print(is_prime(29))

A True

B False

C None

D Error

💡 Hint

Check divisors from 2 up to square root of the number.

29 is a prime number because it has no divisors other than 1 and itself.

❓ Predict Output

intermediate

Output of prime check for number 1

What is the output of this code when checking if 1 is prime?

DSA Python

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

print(is_prime(1))

A True

B False

C None

D Error

💡 Hint

Numbers less than or equal to 1 are not prime.

1 is not a prime number by definition.

🔧 Debug

advanced

Identify the error in prime check code

What error does this code produce when checking if 10 is prime?

DSA Python

def is_prime(n):
    if n <= 1
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

print(is_prime(10))

A No error, outputs False

B TypeError

C NameError

D SyntaxError

💡 Hint

Check the line with the if statement for missing punctuation.

The if statement is missing a colon, causing a SyntaxError.

❓ Predict Output

advanced

Output of prime check for number 25

What is the output of this code when checking if 25 is prime?

DSA Python

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

print(is_prime(25))

A False

B True

C None

D Error

💡 Hint

Check if 25 has divisors other than 1 and itself.

25 is divisible by 5, so it is not prime.

🧠 Conceptual

expert

Why check divisors only up to square root?

Why does the prime check function only test divisors up to the square root of the number?

A Because the square root is the largest possible divisor

B Because numbers larger than the square root are always prime

C Because any factor larger than the square root pairs with a smaller factor already checked

D Because checking beyond the square root causes runtime errors

💡 Hint

Think about factor pairs and multiplication.

If a number has a factor larger than its square root, it must pair with a smaller factor already checked.

Practice

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

easy

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

B. It is divisible by 2 only.

C. It is an even number greater than 2.

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.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime means only divisible by 1 and itself [OK]

Common Mistakes:

• Thinking even numbers are always prime
• Confusing prime with odd numbers
• Believing prime numbers have multiple divisors

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

easy

A. for i in range(2, n): if n % i != 0: return False; return True

B. for i in range(1, n): if n % i == 0: return False; return True

C. for i in range(2, n): if n % i == 0: return False; return True

D. for i in range(2, n): if n % i == 1: return False; return True

Solution

1. Step 1: Analyze the loop range and condition

   for i in range(2, n): if n % i == 0: return False; return True checks divisibility from 2 to n-1, which is correct for prime checking.

2. Step 2: Check the condition for returning False

   If any divisor divides n evenly (remainder 0), return False; else True after loop ends.

3. Final Answer:

   for i in range(2, n): if n % i == 0: return False; return True -> Option C

4. Quick Check:

   Check divisors from 2 to n-1 for remainder 0 [OK]

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

Common Mistakes:

• Starting loop from 1 instead of 2
• Checking for remainder not equal to zero
• Checking if remainder equals 1 instead of 0

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

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

print(is_prime(11))

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Check if n is less than or equal to 1

   Since 11 > 1, skip the first return False.

2. Step 2: Loop from 2 to sqrt(11) + 1 (which is 4)

   Check divisibility by 2 and 3; 11 % 2 != 0 and 11 % 3 != 0, so loop ends without returning False.

3. Step 3: Return True after loop

   No divisor found, so function returns True.

4. Final Answer:

   True -> Option A

5. Quick Check:

   11 is prime, so output is True [OK]

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

Common Mistakes:

• Looping up to n instead of sqrt(n)
• Returning False too early
• Not handling n <= 1 case

4. Find the error in this prime checking function and select the correct fix:

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
        else:
            return True

medium

A. Change range to start from 1 instead of 2

B. Change if condition to n % i != 0

C. Add return True inside the else block

D. Remove the else block inside the loop to return True after loop ends

Solution

1. Step 1: Identify the problem with else inside the loop

   The else causes the function to return True on first non-divisor, which is incorrect.

2. Step 2: Fix by removing else and returning True after loop

   Return True only after checking all divisors without finding any.

3. Final Answer:

   Remove the else block inside the loop to return True after loop ends -> Option D

4. Quick Check:

   Return True only after full divisor check [OK]

Hint: Return True after loop, not inside it [OK]

Common Mistakes:

• Returning True too early inside loop
• Starting loop from 1
• Changing condition to wrong remainder check

5. You want to check if a large number n is prime efficiently. Which approach is best?

hard

A. Check divisibility from 2 to n-1

B. Check divisibility from 2 to sqrt(n)

C. Check divisibility only by 2 and 3

D. Check divisibility from 1 to n

Solution

1. Step 1: Understand the efficiency of divisor checking

   Checking up to n-1 or n is slow for large n; checking only 2 and 3 misses other divisors.

2. Step 2: Use the mathematical fact that divisors come in pairs

   If n has a divisor greater than sqrt(n), it must have a corresponding divisor less than sqrt(n).

3. Step 3: Check divisibility only up to sqrt(n)

   This reduces the number of checks drastically and is the best approach.

4. Final Answer:

   Check divisibility from 2 to sqrt(n) -> Option B

5. Quick Check:

   Divisors up to sqrt(n) suffice for prime check [OK]

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

Common Mistakes:

• Checking all numbers up to n
• Checking only 2 and 3
• Starting divisor check from 1