Given two positive integers start and end. The task is to write a Python program to print all Prime numbers in an Interval.
Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are {2, 3, 5, 7, 11, ….}.
Python Program for Prime Number
The idea to solve this problem is to iterate the val from start to end using a Python loop and for every number, if it is greater than 1, check if it divides n. If we find any other number which divides, print that value.
Python3
# Python program to print all# prime number in an intervaldef prime(x, y): prime_list = [] for i in range(x, y): if i == 0 or i == 1: continue else: for j in range(2, int(i/2)+1): if i % j == 0: break else: prime_list.append(i) return prime_list# Driver programstarting_range = 2ending_range = 7lst = prime(starting_range, ending_range)if len(lst) == 0: print("There are no prime numbers in this range")else: print("The prime numbers in this range are: ", lst) |
The prime numbers in this range are: [2, 3, 5]
Time Complexity: O(N2), where N is the size of the range.
Auxiliary Space: O(N), since N extra space has been taken.
Optimized way to find a Prime Number
The idea to solve this problem is to iterate the value from start to end using a for loop and for every number if it is divisible by any number except 1 and itself (prime number definition) then the flag variable will become 1. And in the next block if the flag value is zero then the only element will be appended to the list.
Step and implementation:
Step 1: Declare the flag and list.
Step 2: We will check the elements if it is divisible or not. (prime number definition)
Step 3: If divisible then flag =1 and break. if not divisible then flag =0.
Step 4: If flag=0, then the element is appended to the list.
Step 5: Return the list.
Python3
# Python program to print all# prime number in an intervaldef prime(starting_range, ending_range): lst=[] flag=0 #Declaring flag variable for i in range(starting_range, ending_range):#elements range between starting and ending range for j in range(2,i): if(i%j==0): #checking if number is divisible or not flag=1 #if number is divisible, then flag variable will become 1 break else: flag=0 if(flag==0): #if flag variable is 0, then element will append in list lst.append(i) return lst# Driver programstarting_range = 2ending_range = 7lst = prime(starting_range, ending_range)if len(lst) == 0: print("There are no prime numbers in this range")else: print("The prime numbers in this range are: ", lst) |
The prime numbers in this range are: [2, 3, 5]
Time Complexity: O(N2), where N is the size of the range.
Auxiliary Space: O(N): since N extra space has been taken
Sieve of Eratosthenes Method:
The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than N when N is smaller than 10 million or so.
Steps and implementation:
- Create a boolean array prime[srt to n] and initialize all its entries as true.
- Mark prime[0] and prime[1] as false because they are not prime numbers.
- Starting from p = srt, for each prime number p less than or equal to the square root of n, mark all multiples of p greater than or equal to p*p as composite by setting prime[i] to false.
- Finally, print all prime numbers between srt and n.
Below is the implementation:
Python3
# Python program to find the prime numbers# between a given interval using Sieve of Eratosthenesimport mathdef SieveOfEratosthenes(srt, n): # Create a boolean array "prime[srt to n]" and # initialize all entries it as true. A value in # prime[i] will finally be false if i is Not a prime, # else true. prime = [True for i in range(n + 2 - srt)] prime[0] = False prime[1] = False for p in range(srt, int(math.sqrt(n))+1): # If prime[p] is not changed, then it is a prime if prime[p] == True: # Update all multiples of p greater than or # equal to the square of it numbers which are # multiple of p and are less than p^2 are # already been marked. for i in range(p*p, n+1, p): prime[i] = False # Print all prime numbers for p in range(srt, n+1): if prime[p]: print(p, end=" ")# Driver Codeif __name__ == "__main__": srt = 1 end = 10 SieveOfEratosthenes(srt, end)# This code is contributed by Susobhan Akhuli |
2 3 5 7
Complexity Analysis:
Time Complexity:
The time complexity of the Sieve of Eratosthenes algorithm is O(n*log(log(n))) as it iterates over all numbers from 2 to n and removes all the multiples of each prime number.
In this code, the algorithm is applied only to a range [srt, n], which reduces the time complexity to O((n-srt+1)*log(log(n))) for the range [srt, n]. The loop for marking the multiples of each prime number iterates from p*p to n, which takes O((n-srt+1)*log(log(n))) time. Therefore, the overall time complexity of this code is O((n-srt+1)*log(log(n))).
Auxiliary Space:
The space complexity of the algorithm is O(n), which is the size of the boolean array prime. However, the size of the array is reduced to n+2-srt, which is the size of the array required for the given range [srt, n]. Therefore, the auxiliary space complexity of the code is O(n-srt+1).
To know more check Sieve of Eratosthenes.
Optimized Sieve of Eratosthenes Method: (Bitwise Sieve Method)
One optimization of the above method is, we have skipped all even numbers altogether. We reduce the size of the prime array to half. We also reduce all iterations to half.
Below is the implementation:
Python3
# Python program to Print all Prime numbers in an Interval# using simple optimized Sieve of Eratosthenes# to reduce size of prime array to half and# reducing iterations.def bitwiseSieve(srt, n): # prime[i] is going to store # true if if i*2 + 1 is composite. prime = [0]*int(n / 2); # 2 is the only even prime so # we can ignore that. Loop # starts from 3. if (srt%2 == 0): srt += 1 if(srt <= 2): srt = 3 i = srt while(i * i < n): # If i is prime, mark all its # multiples as composite if (prime[int(i / 2)] == 0): j = i * i; while(j < n): prime[int(j / 2)] = 1; j += i * 2; i += 2; # writing 2 separately print(2,end=" "); # Printing other primes i = 3; while(i < n): if (prime[int(i / 2)] == 0): print(i,end=" "); i += 2;# Driver codeif __name__=='__main__': srt = 1 end = 10 bitwiseSieve(srt, end)# This code is contributed by Susobhan Akhuli |
2 3 5 7
Time Complexity: O(n*log(log n)), where n is the difference between the intervals.
Space Complexity: O(n)
