Check for Prime Numbers in Python

Check for Prime Numbers in Python

A prime number is a number greater than 1 that has no divisors other than 1 and itself. Efficiently checking for primes is a classic coding problem.

Efficient Solution (Check up to Square Root)

import math

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

print(is_prime(17))   # True
print(is_prime(18))   # False

Why Square Root?

If a number n has a factor greater than its square root, the corresponding paired factor must be less than the square root. So we only need to check up to sqrt(n), making the algorithm O(√n) instead of O(n).

Find All Primes up to N (Sieve of Eratosthenes)

def sieve_of_eratosthenes(limit):
    primes = [True] * (limit + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if primes[i]:
            for j in range(i*i, limit + 1, i):
                primes[j] = False
    return [i for i, v in enumerate(primes) if v]

print(sieve_of_eratosthenes(30))
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Key Takeaway

Always check divisibility up to sqrt(n) for efficiency. Use the Sieve of Eratosthenes when you need all primes up to a given limit.