Python Programs to Find Prime Numbers within a Range

A Prime Number is a number that can only be divided by itself and 1 without remainders (e.g., 2, 3, 5, 7, 11).

In this article, we discuss the simple methods in Python to find prime numbers within a range. Let’s look at each of the methods with examples.

1. Using loop for Checking Divisibility

This simple Python method checks for prime numbers by iterating through all numbers in the range using for loop and range() function and checking if they are divisible by any number other than one and themselves.

Code Example

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

start = 50
end = 100
primes = []
for num in range(start, end + 1):
    if is_prime(num):
        primes.append(num)
print(primes)Code language: Python (python)

Output:

[53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Explanation

• We use a for loop to iterate each number from start to end and check whether it is prime by using is_prime() function.
• In is_prime() function, we loop from 2 to num and check if num is divisible by any number other than one and itself.
  • Using the modulo operator, we can find the divisor of the given num.
  • num % i returns the remainder when num is divided by i.
  • num % i == 0 checks if the remainder is zero, meaning num is perfectly divisible by i. Hence returns False as it’s not a prime number otherwise, returns True.
• If the number is prime, we add it to the list primes.
• This method is inefficient for larger numbers because of unnecessary modulo operation till num.

2. Optimized Method (Check up to √n)

In this Python method, instead of checking divisibility up to the number itself, we only need to check up to the square root of the number. This optimization reduces the number of unnecessary checks.

The math.sqrt() function in Python is used to calculate the square root of a given number.

For instance, consider n = 49:

• The square root of 49 is 7.
• The loop iterates only through numbers 2 to 7, skipping checks for 8 through 48.
• When it finds 49 % 7 == 0, confirming that 49 is not a prime number.

It is more efficient than the above basic method.

Code Example

import math

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

start = 50
end = 100
primes = []
for num in range(start, end + 1):
    if is_prime_optimized(num):
        primes.append(num)
print(primes)Code language: Python (python)

Output:

[53, 59, 61, 67, 71, 73, 79, 83, 89, 97]Code language: Python (python)