Checking for Prime Numbers in Python
A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. In other words, a prime number has exactly two distinct positive divisors: 1 and itself. To determine if a number is prime, one efficient approach is to check for factors only up to the square root of the number.
Here’s a Python function that implements this logic effectively:
def is_prime(n):
"""Check if the number n is a prime number.
Args:
n (int): The number to check.
Returns:
bool: True if n is prime, False otherwise.
"""
# Check for numbers less than 2
if n <= 1:
return False
# Check for 2 and 3, which are prime
if n <= 3:
return True
# Eliminate even numbers greater than 2
if n % 2 == 0:
return False
# Check for factors from 3 to the square root of n
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
# Example usage
number = 29
if is_prime(number):
print(f"{number} is a prime number.")
else:
print(f"{number} is not a prime number.")
Explanation of the Function
1. Initial Checks:
- The function begins by checking if n is less than or equal to 1. Since prime numbers are defined as greater than 1, it returns False for these values.
- It then directly returns True for inputs 2 and 3, both of which are prime.
2. Even Number Elimination:
- It immediately checks if the number is even (except for 2) and returns False since no even number greater than 2 can be prime.
3. Iterative Factor Check:
- The loop checks for potential factors from 3 to the square root of n. By iterating only over odd numbers (increments of 2), the function skips even numbers, thus reducing unnecessary checks.
4. Return Value:
- If no factors are found within the loop, the function concludes that n is prime and returns True.
Performance Consideration
This algorithm is efficient for checking primality, particularly for numbers that are not excessively large. The time complexity is approximately \(O(\sqrt{n})\), making it well-suited for practical applications such as generating a list of primes or validating prime candidates in mathematical computations.