Understanding the Problem

Before diving into the code, it’s essential to have a clear understanding of what prime numbers are and the problem at hand. Prime numbers are integers greater than 1 that have no divisors other than 1 and themselves. Our goal is to write a program that can identify all the prime numbers within a given range specified by the user.

Developing the Algorithm

To find prime numbers within a given range, we can use a simple algorithm known as the “Sieve of Eratosthenes.” This algorithm works by iteratively eliminating multiples of each prime number found, gradually narrowing down the list of potential primes.

The steps involved in the algorithm are as follows:

1. Create a list of numbers from the starting point to the ending point of the range.
2. Start with the first number in the list and mark it as a prime number.
3. Eliminate all multiples of the current prime number from the list.
4. Move to the next unmarked number and repeat step 3 until all numbers have been processed.
5. The remaining unmarked numbers in the list are prime numbers within the given range.

Writing the Python Code

Now, let’s implement the algorithm in Python. Below is the code snippet that accomplishes this task:

# Python program to print prime numbers within a given range

def print_prime_numbers(start, end):
    primes = []
    prime_flags = [True] * (end + 1)
    p = 2

    while p * p <= end:
        if prime_flags[p] is True:
            for i in range(p * p, end + 1, p):
                prime_flags[i] = False
        p += 1

    for p in range(start, end + 1):
        if prime_flags[p]:
            primes.append(p)

    return primes

start_range = int(input("Enter the starting range: "))
end_range = int(input("Enter the ending range: "))

prime_numbers = print_prime_numbers(start_range, end_range)

print("Prime numbers within the given range are:")
for prime in prime_numbers:
    print(prime, end=" ")

O/P

Enter the starting range: 1
Enter the ending range: 100
Prime numbers within the given range are:

1 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

Time Complexity

The time complexity of the code for finding prime numbers within a given range using the Sieve of Eratosthenes algorithm is O(n log log n), where n represents the ending range of the input.

Code Explanation

Let’s go through the code to understand how it works:

1. The print_prime_numbers function takes the starting and ending range as input parameters.

2. A list called primes is initialized to store the prime numbers found within the range.

3. A Boolean list, prime_flags, is created with True values for each number in the range.

4. The algorithm starts with the first prime number, 2, and iterates until the square root of the ending range.

5. Within the loop, it checks if a number is marked as prime. If it is, it eliminates its multiples by updating the prime_flags list accordingly.

6.After the loop completes, the function iterates through the range again and appends the remaining prime numbers to the primes list.

7. The function returns the list of prime numbers.

8. User input is taken for the starting and ending range.

9. The print_prime_numbers function is called, and the resulting prime numbers are stored in prime_numbers.

10. Finally, the prime numbers are printed to the console.

Dry Run

To ensure a clear understanding, let’s perform a dry run of the code with an example:

1. Suppose the user enters a starting range of 10 and an ending range of 30.

2. The function is called with start_range = 10 and end_range = 30.

3. The algorithm begins, initializing primes as an empty list and prime_flags as a list of True values up to 30.

4. Starting with the first prime number, 2, it eliminates its multiples from the prime_flags list: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.

5. The loop moves to the next unmarked number, 3, and eliminates its multiples: 9, 15, 21, 27.

6. The loop proceeds to the next unmarked number, 5, and eliminates its multiples: 25.

7. The remaining numbers in the prime_flags list that are marked as True (prime) are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].

8. The function returns this list of prime numbers.

9. The prime numbers within the given range are printed to the console: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.