Check if Number is Prime in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a number is prime by testing divisibility starting from 2.

DSA Python

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, [1]):
        if num % i == 0:
            return False
    return True

Drag options to blanks, or click blank then click option'

Anum

Bnum + 1

Cnum // 2 + 1

Dint(num ** 0.5) + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using num + 1 includes num itself, incorrectly returning False for primes.

Using int(num ** 0.5) + 1 is an optimization but not for this easy task.

The loop must check divisors from 2 up to num (exclusive) to find any divisor. Using num ensures the loop checks up to num-1.

2fill in blank

medium

Complete the code to optimize prime check by testing divisors only up to the square root of the number.

DSA Python

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, [1]):
        if num % i == 0:
            return False
    return True

Drag options to blanks, or click blank then click option'

Anum // 2

Bnum

Cint(num ** 0.5) + 1

Dnum // 3

Attempts:

3 left

💡 Hint

Common Mistakes

Checking up to num wastes time.

Using num // 2 is less efficient.

Checking divisors only up to the square root of num is enough to determine primality efficiently.

3fill in blank

hard

Fix the error in the code to correctly check if a number is prime by returning False immediately when a divisor is found.

DSA Python

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

Drag options to blanks, or click blank then click option'

A%

B//

C*

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using == instead of % causes a syntax error.

Using // or * does not check divisibility.

The modulo operator % checks if num is divisible by i with no remainder, which means i is a divisor.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps numbers to True if prime, False otherwise, for numbers 2 to 10.

DSA Python

primes = {num: is_prime(num) for num in [1] if num [2] 1}

Drag options to blanks, or click blank then click option'

Arange(2, 11)

Brange(1, 11)

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using range(1, 11) includes 1 which is not prime.

Using >= includes 1 which is not prime.

We want numbers from 2 to 10, so range(2, 11) is correct. The condition num > 1 filters numbers greater than 1.

5fill in blank

hard

Fill all three blanks to create a list comprehension that lists all prime numbers between 10 and 20.

DSA Python

prime_numbers = [[1] for n in [2] if is_prime([3])]

Drag options to blanks, or click blank then click option'

An

Brange(10, 21)

Drange(11, 20)

Attempts:

3 left

💡 Hint

Common Mistakes

Using range(11, 20) excludes 10 and 20.

Using different variables in the comprehension causes errors.

The list comprehension iterates over numbers 10 to 20 inclusive using range(10, 21), checks if each number n is prime, and collects n if true.

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