Prime Numbers and Finding Primes in a Range

A prime number is a natural number greater than 1 that is not divisible by any positive integers other than 1 and itself. There are infinitely many prime numbers.

Below are examples of how to find prime numbers within a specified range using different methods:

Example 1: Output Prime Numbers in a Specified Range

#!/usr/bin/python3

# Output prime numbers within a specified range

# Take input from the user
lower = int(input("Enter the lower bound of the range: "))
upper = int(input("Enter the upper bound of the range: "))

for num in range(lower, upper + 1):
    # Prime numbers are greater than 1
    if num > 1:
        for i in range(2, num):
            if (num % i) == 0:
                break
        else:
            print(num)

Example Output:

$ python3 test.py
Enter the lower bound of the range: 1
Enter the upper bound of the range: 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

Trial Division Method

Trial division is a basic algorithm that tests each number for divisibility to determine if it is a prime number.

Example Code:

def is_prime(n):
    """Check if a number is prime"""
    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

def primes_in_range(start, end):
    """Print prime numbers in a specified range"""
    for num in range(start, end + 1):
        if is_prime(num):
            print(num)

# Example: Print prime numbers from 10 to 50
primes_in_range(10, 50)

Sieve of Eratosthenes Method

The Sieve of Eratosthenes is a more efficient algorithm, especially suitable for finding all prime numbers up to a large number.

Example Code:

def sieve_of_eratosthenes(max_num):
    """Find all prime numbers up to max_num using the Sieve of Eratosthenes"""
    sieve = [True] * (max_num + 1)
    sieve[0] = sieve[1] = False  # 0 and 1 are not prime
    p = 2
    while p * p <= max_num:
        if sieve[p]:
            for multiple in range(p * p, max_num + 1, p):
                sieve[multiple] = False
        p += 1
    return [p for p, is_prime in enumerate(sieve) if is_prime]

def primes_in_range(start, end):
    """Print prime numbers in a specified range"""
    primes = sieve_of_eratosthenes(end)
    for num in primes:
        if num >= start:
            print(num)

# Example: Print prime numbers from 10 to 50
primes_in_range(10, 50)

These examples illustrate different methods to find prime numbers within a given range using Python.