Python programs / Numbers / Prime numbers in a range

Python Program to Find Prime Numbers in a Range

Beginner Numbers

Lists every prime number between two numbers, such as 10 and 50, by checking each number in turn.

This program lists the prime numbers between two numbers. A prime is a whole number greater than 1 that only 1 and itself divide exactly, so from 10 to 50 the primes are 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47: eleven of them. The program checks every number in the range and keeps the ones that pass.

Program

def is_prime(number):
    """True if number is a prime number."""
    if number < 2:
        return False
    divisor = 2
    while divisor * divisor <= number:
        if number % divisor == 0:
            return False
        divisor += 1
    return True


def primes_between(start, end):
    """The prime numbers from start to end, both included."""
    primes = []
    for number in range(start, end + 1):
        if is_prime(number):
            primes.append(number)
    return primes


print("Primes from 10 to 50:", primes_between(10, 50))
print("Primes from 1 to 10:", primes_between(1, 10))

Open in the editor Download primes_in_range.py

Output

Primes from 10 to 50: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Primes from 1 to 10: [2, 3, 5, 7]

How it works

  1. is_prime turns down numbers below 2 first: 0 and 1 aren't prime.
  2. It tries each divisor from 2 while divisor * divisor <= number. If one goes into the number exactly, the number isn't prime. Divisors above the square root needn't be tried, as each pairs with one below the square root: 21 = 3 × 7, and the loop finds 3 first.
  3. No divisor was found, so the number is prime.
  4. primes_between starts with an empty list for the primes it finds.
  5. range(start, end + 1) goes through every number from start to end: the + 1 is there because range() stops before its end. Each number that is_prime passes is added to the list.
  6. The list of primes goes back to the caller.
  7. The program lists the primes from 10 to 50, then from 1 to 10, which leaves out 1.

Two small functions keep each job short: is_prime answers a question about one number, and primes_between uses that answer without needing to know how it was found.

Other ways to write it

With a list comprehension

The loop that builds the list fits in one list comprehension:

def is_prime(number):
    if number < 2:
        return False
    divisor = 2
    while divisor * divisor <= number:
        if number % divisor == 0:
            return False
        divisor += 1
    return True

print([n for n in range(10, 51) if is_prime(n)])

With the Sieve of Eratosthenes

For a large range, crossing out multiples is faster than testing each number. The sieve starts with every number up to end marked as possibly prime, and for each prime it reaches, crosses out its multiples. It starts at number * number because the smaller multiples were crossed out by smaller primes.

def primes_between(start, end):
    is_prime = [True] * (end + 1)
    for number in range(2, end + 1):
        if is_prime[number]:
            for multiple in range(number * number, end + 1, number):
                is_prime[multiple] = False
    return [n for n in range(max(start, 2), end + 1) if is_prime[n]]

print(primes_between(10, 50))

Try it yourself

  • List the primes from 1 to 100: there are 25.
  • Print only how many primes there are with len(): from 1 to 1000 there are 168.
  • Find the twin primes from 10 to 50, pairs that differ by 2: (11, 13), (17, 19), (29, 31) and (41, 43).
  • Add up the primes from 10 to 50 with sum(): the total is 311.

More numbers programs

Share this program