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

Check if Number is Prime

📖 Scenario: You are helping a friend who wants to check if a number is prime. A prime number is a number greater than 1 that has no divisors other than 1 and itself.Imagine you have a list of numbers and want to find out which ones are prime.

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

📋 What You'll Learn

Create a variable called number with the exact value 29.

Create a variable called is_prime and set it to True.

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

Inside the loop, if number is divisible by i, set is_prime to False and break the loop.

Print "Prime" if is_prime is True, otherwise print "Not Prime".

💡 Why This Matters

🌍 Real World

Prime numbers are important 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 a variable called number and set it to the exact value 29.

DSA Python

# Create a variable called number and set it to 29
# Your code here

Hint

Use number = 29 to create the variable.

2

Set up the prime flag

Create a variable called is_prime and set it to True.

DSA Python

number = 29
# Create a variable called is_prime and set it to True
# Your code here

Hint

Use is_prime = True to start assuming the number is prime.

3

Check divisors with a loop

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

DSA Python

number = 29
is_prime = True
# Use a for loop with i from 2 to number - 1
# Inside the loop, check if number is divisible by i
# If yes, set is_prime to False and break
# Your code here

Hint

Use for i in range(2, number): and check divisibility with number % i == 0.

4

Print if the number is prime

Print "Prime" if is_prime is True, otherwise print "Not Prime".

DSA Python

number = 29
is_prime = True
for i in range(2, number):
    if number % i == 0:
        is_prime = False
        break
# Print "Prime" if is_prime is True else print "Not Prime"
# Your code here

Hint

Use an if statement to print "Prime" or "Not Prime" based on is_prime.

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