Checking if a number is prime is a fundamental programming task. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
In this tutorial, we will explore different ways to check for primality in Python, from the naive approach to more optimized solutions.
The Naive Approach
The simplest way to check if a number n is prime is to divide it by every number from 2 up to n-1. If any division results in a remainder of 0, then n is not prime.
def is_prime(num):
if num <= 1:
return False
for i in range(2, num):
if num % i == 0:
return False
return True
This works, but it’s slow for large numbers. The time complexity is O(N).
Optimizing the Loop: Halfway Point
We don’t need to check all numbers up to n-1. The largest possible factor of n (other than n itself) is n/2. So we can stop checking at n // 2 + 1.
def is_prime_v2(num):
if num <= 1:
return False
for i in range(2, (num // 2) + 1):
if num % i == 0:
return False
return True
This cuts the work in half, but the complexity is still O(N).
The Efficient Approach: Square Root Optimization
We can do much better. If a number n is composite (not prime), it must have a factor less than or equal to its square root.
Why? If n = a * b, then one of the factors must be less than or equal to sqrt(n). If both were greater than sqrt(n), their product would be greater than n.
So we only need to check divisors up to int(sqrt(n)) + 1.
import math
def is_prime_optimized(num):
if num <= 1:
return False
if num == 2:
return True
if num % 2 == 0:
return False # Even numbers > 2 are not prime
limit = int(math.sqrt(num)) + 1
for i in range(3, limit, 2): # Check only odd numbers
if num % i == 0:
return False
return True
Complexity Analysis: * Time Complexity: O(sqrt(N)). This is significantly faster for large numbers.
Summary
When checking for primes:
1. Handle edge cases (numbers <= 1).
2. Check for divisibility by 2.
3. Loop from 3 up to the square root of n, checking only odd numbers.
This optimized approach is efficient enough for most competitive programming and interview scenarios.
Written by
Abdur-Rahmaan Janhangeer
Chef
Python author of 7+ years having worked for Python companies around the world
Suggested Posts
Understanding Armstrong Numbers in Python
In this post, we’ll explore a classic beginner programming problem: Armstrong Numbers. What is an Ar...
Daily Coding Problem #1: Two Sum Solution in Python
This problem was recently asked by Google and is a classic interview question often referred to as “...
The Zen Of Python: A Most In Depth Article
Note: I wrote a quite complete article on the Zen but for some reason it went down in seo history. I...
