How to Find Prime Numbers in a Range Using Python

The simplest way to find prime numbers in a range using Python is a loop over every number from low to high that keeps the ones that have no divisor between 2 and their square root. One list comprehension does it:

primes = [n for n in range(low, high + 1)
          if n > 1 and all(n % d for d in range(2, math.isqrt(n) + 1))]

I ran every listing below with Python 3.12.5 and SymPy 1.14.0 and pasted the real output.

You’ll see the loop, user input, the Sieve of Eratosthenes, a segmented sieve for huge numbers, and SymPy’s primerange().

Find prime numbers in a range with a for loop

A prime is a whole number above 1 divisible only by 1 and itself. Testing divisors up to math.isqrt(n) (the integer square root) is enough; any larger factor pairs with a smaller one.

import math

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

def primes_in_range(low, high):
    return [n for n in range(low, high + 1) if is_prime(n)]

print("Prime years 2000-2030:", primes_in_range(2000, 2030))
print("Primes -5 to 5:", primes_in_range(-5, 5))

Output:

Prime years 2000-2030: [2003, 2011, 2017, 2027, 2029]
Primes -5 to 5: [2, 3, 5]

The high + 1 matters because range() stops before its end. The filter is a list comprehension in Python; if you only need a yes or no for one value, use my guide to checking if a number is prime in Python.

How do you read the range from the user?

Your program breaks when someone types a word. Wrap input() in a small while loop in Python that asks again:

import math

def is_prime(n):
    return n >= 2 and all(n % d for d in range(2, math.isqrt(n) + 1))

def read_int(prompt):
    while True:
        text = input(prompt).strip()
        if text.lstrip("-").isdigit():
            return int(text)
        print("  Please type a whole number.")

low = read_int("Start of range: ")
high = read_int("End of range: ")
if low > high:
    low, high = high, low

primes = [n for n in range(low, high + 1) if is_prime(n)]
print(f"{len(primes)} primes between {low} and {high}:")
print(*primes, sep=", ")

Output:

Start of range: 100
End of range: abc
  Please type a whole number.
End of range: 150
10 primes between 100 and 150:
101, 103, 107, 109, 113, 127, 131, 137, 139, 149

The count is just len(primes). For the total, use sum(primes), as in the sum of prime numbers in a range in Python.

Find primes in a large range with the Sieve of Eratosthenes

The Sieve of Eratosthenes starts with a list of True flags and crosses out the multiples of each prime, so whatever’s left is prime.

import math

def sieve(limit):
    flags = [True] * (limit + 1)
    flags[0] = flags[1] = False
    for i in range(2, math.isqrt(limit) + 1):
        if flags[i]:
            flags[i * i :: i] = [False] * len(range(i * i, limit + 1, i))
    return flags

def primes_in_range(low, high):
    flags = sieve(high)
    return [n for n in range(max(low, 2), high + 1) if flags[n]]

print("Count 1 to 1,000,000:", len(primes_in_range(1, 1_000_000)))
print("Primes 999,900-1,000,000:", primes_in_range(999_900, 1_000_000))

Output:

Count 1 to 1,000,000: 78498
Primes 999,900-1,000,000: [999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]

It finds all 78,498 primes up to one million without a single division.

For ranges that start at 1, the Python program to print prime numbers from 1 to N covers more.

Find primes between two large numbers with a segmented sieve

A plain sieve needs a flag for every number up to high, which is a billion flags for a window above one billion.

A segmented sieve keeps flags only for the window and crosses them out with the primes up to the square root of high.

import math
import sympy

def primes_between(low, high):
    low = max(low, 2)
    flags = [True] * (high - low + 1)          # flags for the window only
    root = math.isqrt(high)
    small = [p for p in range(2, root + 1) if all(p % d for d in range(2, math.isqrt(p) + 1))]
    for p in small:
        start = max(p * p, (low + p - 1) // p * p)   # first multiple in the window
        for multiple in range(start, high + 1, p):
            flags[multiple - low] = False
    return [low + i for i, f in enumerate(flags) if f]

low, high = 1_000_000_000, 1_000_000_100
found = primes_between(low, high)
print(f"{len(found)} primes between {low:,} and {high:,}:")
print(found)
print("Matches SymPy:", found == list(sympy.primerange(low, high + 1)))

Output:

7 primes between 1,000,000,000 and 1,000,000,100:
[1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097]
Matches SymPy: True

To get only the first prime after a value, see finding the next largest prime number in Python.

Find primes in a range with SymPy primerange()

SymPy (pip install sympy) has this built in: primerange(a, b) yields the primes and primepi(n) counts primes up to n.

from sympy import primerange, primepi

print(list(primerange(10, 47)))       # stop is excluded: no 47
print(list(primerange(10, 47 + 1)))   # add 1 to include it

print("Primes 500,000-600,000:", primepi(600_000) - primepi(499_999))

Output:

[11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Primes 500,000-600,000: 7560

primepi(high) - primepi(low - 1) counts without a list. SymPy also helps when you generate a random prime number in Python.

Try these number programs once primes feel easy:

• Perfect number in Python
• Armstrong number in Python
• Fibonacci series in Python
• Factorial of a number in Python

Frequently asked questions