Check if Number is Prime in DSA Python

Mental Model

A prime number is a number greater than 1 that has no divisors other than 1 and itself. To check if a number is prime, we test if it can be divided evenly by any number from 2 up to its square root.

Analogy: Imagine you have a group of identical candies and want to split them evenly into smaller groups without leftovers. If you can only split them into one big group or single candies, then the number of candies is prime.

Number: 7
Check divisors: 2
7 % 2 != 0
No divisor found -> prime

Dry Run Walkthrough

Input: number = 7

Goal: Determine if 7 is a prime number

Step 1: Check if number is less than or equal to 1

7 > 1, continue checking

Why: Numbers less than or equal to 1 are not prime

Step 2: Check divisibility by 2

7 % 2 = 1 (not zero)

Why: If divisible, number is not prime; here it is not divisible

Step 3: Loop ends (limit = int(math.isqrt(7)) = 2)

No divisors found

Why: No divisor found up to sqrt(7), so number is prime

Result:

7 is prime

Annotated Code

DSA Python

import math

def is_prime(number: int) -> bool:
    if number <= 1:
        return False  # Numbers <= 1 are not prime
    limit = int(math.isqrt(number))  # Only check up to square root
    for divisor in range(2, limit + 1):
        if number % divisor == 0:
            return False  # Found a divisor, not prime
    return True  # No divisors found, number is prime

# Driver code
num = 7
if is_prime(num):
    print(f"{num} is prime")
else:
    print(f"{num} is not prime")

if number <= 1:

Check if number is too small to be prime

limit = int(math.isqrt(number))

Calculate the integer square root to limit divisor checks

for divisor in range(2, limit + 1):

Check divisors from 2 up to square root

if number % divisor == 0:

If divisible, number is not prime

return True

No divisors found, number is prime

Output

7 is prime

Complexity Analysis

Time: O(√n) because we only check divisors up to the square root of the number

Space: O(1) because we use a fixed amount of extra space regardless of input size

vs Alternative: Checking all numbers up to n would be O(n), which is slower; limiting to √n reduces checks significantly

Edge Cases

number = 1

Returns False because 1 is not prime

DSA Python

if number <= 1:

number = 2

Returns True because 2 is the smallest prime number

DSA Python

for divisor in range(2, limit + 1):

number = 0 or negative numbers

Returns False because primes are positive integers greater than 1

DSA Python

if number <= 1:

When to Use This Pattern

When you need to check if a number has no divisors other than 1 and itself, use the prime check pattern by testing divisibility up to the square root.

Common Mistakes

Mistake: Checking divisibility up to the number itself instead of square root
Fix: Limit divisor checks to the integer square root to improve efficiency

Mistake: Not handling numbers less than or equal to 1 correctly
Fix: Add a condition to return False for numbers <= 1

Summary

Checks if a number is prime by testing divisibility up to its square root.

Use when you need to quickly determine if a number has no divisors other than 1 and itself.

Only check divisors up to the square root because any larger divisor would have a smaller pair already checked.