Python Program to Print all Prime Numbers in an Interval
Printing all prime numbers in an interval is a common problem in mathematics. It involves finding all prime numbers within a specific range of numbers. The objective of the article is to identify and print all prime numbers within this interval. In Python, there are several approaches to solving this problem, which involve using different algorithms and techniques.
Prime numbers can only be divided by 1 and themselves. Python has different techniques to find them in a given interval, such as trial division of numbers between the interval or by using the Sieve of Eratosthenes algorithm.
Number => 5 => Divided by => 1 and 5 => Prime Number
Number => 6 => Divided by => 1,2,3 and 6 => Not a Prime Number
Print all Prime Numbers in an Interval
Python provides different techniques to find prime numbers in a given interval, and these techniques are explained in detail below. Wiki Link to understand the list of prime numbers
Using trial division
Checking if a number is prime
We need to follow the below steps to check if the number is prime or not
Step 1: If the given number is less than or equal to 1, it is not a prime number.
Step 2: Next, If the number is 2, it is a prime number.
Step 3: Next, If the number is even (i.e., divisible by 2), it is not a prime number.
Step 4: As a final step, Check if the number is divisible by any odd number from 3 to the square root of the number. Then it is not a prime number. else, it is a prime number.
Using the above steps, We have created a function to calculate the prime number
def is_prime(n):
if n <= 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
else:
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
If we provide the number as an input to this function, It will give you either true = Prime number or false = Not a prime number
Example:
print(is_prime(4)) => Output: False print(is_prime(997)) => Output: True
With the above function, Now we can able to find if a given input number is a prime number or not. To move forward, We need to find all the prime numbers within a range of values. For that, We again create a custom function “print_primes_in_interval” to get the start and end range as input and provide all the prime numbers as output.
def print_primes_in_interval(start, end):
primes = []
for num in range(start, end+1):
if is_prime(num):
primes.append(num)
print("Prime numbers in the interval [{}, {}] are:".format(start, end))
print(primes)
In the above code, We have declared an empty list to store all the prime numbers. Then we use the range function to iterate through each number in the interval and check if it is prime using the is_prime function. If it is, we append it to the primes list. At last, we print the list of prime numbers.
Example
To get the list of all prime numbers between 10 and 50. We can call the print_primes_in_interval function with the parameters start=10 and end=50 as shown below
print_primes_in_interval(10, 50)
Output:
Prime numbers in the interval [10, 50] are:
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
With the input values 10 and 50, We have found the prime numbers between them [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Using the Sieve of Eratosthenes method
The Sieve of Eratosthenes is an algorithm for finding all the prime numbers up to a given limit. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.
For example to find all prime numbers within a given interval using the Sieve of Eratosthenes
def print_primes_in_interval(start, end): # create a list of all numbers from start to end nums = [True] * (end + 1) nums[0] = nums[1] = False # iterate through the list and mark all non-prime numbers for i in range(2, int(end**0.5) + 1): if nums[i]: for j in range(i**2, end + 1, i): nums[j] = False # print all prime numbers in the interval primes = [i for i in range(start, end + 1) if nums[i]] print("Prime numbers in the interval [{}, {}] are:".format(start, end)) print(primes)print_primes_in_interval(10, 50)
In the above code, we first create a list called nums of length end + 1, where each element is initially set to True. We then mark all non-prime numbers in the list using the Sieve of Eratosthenes algorithm. At last, we create a list called primes containing all the prime numbers in the interval, and print it.
Output:
Prime numbers in the interval [10, 50] are:
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
45
Using the sympy library
Sympy is a Python library for symbolic mathematics. It provides a number of functions for working with prime numbers. Here’s how to use the sympy library to find all prime numbers within a given interval:
def print_primes_in_interval(start, end):
primes = [i for i in range(start, end + 1) if isprime(i)]
print("Prime numbers in the interval [{}, {}] are:".format(start, end))
print(primes)
print_primes_in_interval(10, 50)
In the above code, we use the isprime function from the sympy library to check if each number in the interval is prime. We then create a list called primes containing all the prime numbers in the interval and print it.
Output:
Prime numbers in the interval [10, 50] are: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Performance Testing
Based on theory, the Sieve of Eratosthenes algorithm generally has better performance than both the trial division method and SymPy’s prime number functions.
Let’s do a quick performance testing on the above three methods. I am using “datetime.datetime.now()” to get the start time and calculating again after code execution is completed and the difference will give you the total time spent on processing the code 🙂
Using the sympy library
start_time = datetime.datetime.now() print_primes_in_interval(10, 9999999) end_time = datetime.datetime.now() print(end_time - start_time)
The total time consumed to find all the prime numbers between 10, and 9999999 is approximately 11 seconds
0:00:11.694692
Using the Sieve of Eratosthenes method
start_time = datetime.datetime.now() print_primes_in_interval(10, 9999999) end_time = datetime.datetime.now() print(end_time - start_time)
The total time consumed to find all the prime numbers between 10, and 9999999 is approximately 1.8 seconds
0:00:01.881594
Using trial division
start_time = datetime.datetime.now() print_primes_in_interval(10, 9999999) end_time = datetime.datetime.now() print(end_time - start_time)
The total time consumed to find all the prime numbers between 10, and 9999999 is approximately 45 seconds
0:00:45.891543
So the theory is actually true, Sieve of Eratosthenes algorithm is better in performance comparing the other 2 methods. Awesome find 🙂
Conclusion
In this article, we’ve looked at three different approaches to finding all prime numbers within a given interval in Python. One is using the Sieve of Eratosthenes algorithm and the second method uses sympy library and the last and final method is by using division to find the prime number. We also did a quick performance test by giving a large range of numbers 10 -> 9999999 and found the Sieve of Eratosthenes algorithm outperformed the other 2 methods. So the choice of methods is based on the use case and the performance 🙂
Good Luck with your Learning !!
Related Topics:
How do you code a Hangman Game in Python?
