Python Check If Number Is Prime (5 Best Ways) : Chris
by: Chris
blow post content copied from Be on the Right Side of Change
click here to view original post
Problem Formulation
A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. This implies it has only two divisors: 1 and itself.
Challenge: Create a Python function that will determine if a number given as input is a prime number or not.
Method 1: Trial Division
The simplest method to check for a prime number is trial division. We check if our number has any divisor other than 1 and itself by testing all integers from 2 to the square root of the number. If no divisors are found, the number is prime.
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
This function first handles the edge case where n is less than or equal to 1. Then it checks for divisors up to the square root of n. If a divisor is found, it returns False; otherwise, it returns True.
Method 2: Sieve of Eratosthenes (For Range Of Numbers)
While not directly a method to check if a single number is prime, the Sieve of Eratosthenes is a classic algorithm for generating a list of primes up to a certain limit. Once the list is generated, we can then check if the number in question is a prime by simply determining if it is in the list.
def is_prime(n):
if n <= 1:
return False
elif n <= 3:
return True
elif n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
The sieve_of_eratosthenes function creates a sieve list, marking non-primes as False. In the is_prime function, we utilize the sieve to determine if n is prime.
Explanation: This function first handles simple cases (numbers less than 2 are not prime, 2 and 3 are prime). It then checks divisibility by 2 and 3 to quickly eliminate multiples of these. After that, it iterates over potential divisors starting from 5, checking divisibility by i and i+2 (skipping even numbers and multiples of 3), up to the square root of n. This isn’t the Sieve of Eratosthenes in its classic form but an efficient way to check for a prime number that shares the spirit of eliminating factors by checking divisibility.
If you’re interested in this algorithm, check out my fun one-liner tutorial:
The Sieve of Eratosthenes in Python
Method 3: 6k +/- 1 Optimization
After observing that all primes greater than 3 are of the form 6k ± 1, we can check for divisors in a more optimized way. This avoids checking multiples of 2 and 3.
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
This code first checks for small numbers (<= 3) and then eliminates numbers divisible by 2 and 3. It then checks for factors of the form 6k ± 1 up to the square root of n.
Method 4: Checking for Primality Using Recursion
Recursion can also be applied to check for a prime number by recursively dividing the number by the current divisor till it either finds a divisor or verifies it’s a prime.
def is_prime_helper(n, divisor):
if n <= 2:
return True if n == 2 else False
if n % divisor == 0:
return False
if divisor * divisor > n:
return True
return is_prime_helper(n, divisor + 1)
def is_prime(n):
return is_prime_helper(n, 2)
This code uses a helper function is_prime_helper which determines if a number n is prime by recursively dividing n by a divisor starting from 2.
Method 5: Using the Fermat’s Little Theorem
Fermat’s Little Theorem can sometimes be used as a probabilistic check. According to the theorem, if n is a prime number, then for any integer a, a^n ≡ a (mod n). This can suggest primality, but beware of Fermat liars.
import random
def is_prime(n):
if n <= 1:
return False
for _ in range(5): # number of trials
a = random.randint(2, n-1)
if pow(a, n-1, n) != 1:
return False
return True
The code tests the theorem with a random a for a certain number of trials. If the theorem doesn’t hold, n is not prime. If it holds for all tests, n is likely prime.
Bonus One-Liner Method 6: Pythonic Way
For aficionados of Python’s expressive one-liners, here’s a succinct way to check for primality.
is_prime = lambda n: n > 1 and all(n % i for i in range(2, int(n**0.5) + 1))
This lambda function uses all to determine if there are no divisors of n from 2 up to the square root of n.
Check out my new Python book Python One-Liners (Amazon Link).
If you like one-liners, you’ll LOVE the book. It’ll teach you everything there is to know about a single line of Python code. But it’s also an introduction to computer science, data science, machine learning, and algorithms. The universe in a single line of Python!
The book was released in 2020 with the world-class programming book publisher NoStarch Press (San Francisco).
Publisher Link: https://nostarch.com/pythononeliners
Summary/Discussion
While there are multiple methods to check if a number is prime in Python, each comes with its own trade-offs in terms of readability, speed, and accuracy.
- Trial division (Method 1) is the simplest but not the most efficient for large numbers.
- The Sieve of Eratosthenes (Method 2) is great for checking primality within a range, but not optimal for a single large number.
- The 6k +/- 1 optimization (Method 3) improves over trial division for individual numbers.
- Recursion (Method 4) and Fermat’s Little Theorem (Method 5) provide additional ways, with recursion as a fundamental approach, and Fermat’s method serving as a fast, probabilistic test.
- Finally, the Pythonic one-liner (Method 6) showcases the power of Python’s expressive syntax, making it ideal for code golfing and small-scale tests.
February 02, 2024 at 02:45PM
Click here for more details...
=============================
The original post is available in Be on the Right Side of Change by Chris
this post has been published as it is through automation. Automation script brings all the top bloggers post under a single umbrella.
The purpose of this blog, Follow the top Salesforce bloggers and collect all blogs in a single place through automation.
============================
Post a Comment