Python Program to Read Print Prime Numbers in a Range using Sieve of Eratosthenes

The Sieve of Eratosthenes is a very old and conventional algorithm for finding all prime numbers that are less or equal to a given number. If the number is less than or equal to 10 million or so, the Eratosthenes sieve is highly effective. You may get a thorough explanation of the algorithm on Wikipedia.

Given the lower limit and upper limit the task is to print prime numbers in the given range using sieve of Eratosthenes in Python.

Examples:

Example1:

Input:

Enter some random upper limit range = 529

Output:

The prime numbers from 1 to 529 are :
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 101 103 107 109 113 127 131 137 139 
149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443
449 457 461 463 467 479 487 491 499 503 509 521 523

Example2:

Input:

Enter some random upper limit range = 129

Output:

The prime numbers from 1 to 129 are :
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 101 103 107 109 113 127

Program to Read Print Prime Numbers in a Range using Sieve of Eratosthenes

Are you new to the java programming language? We recommend you to ace up your practice session with these Basic Java Programs Examples

1)Algorithm

  • Make a Boolean array of size n, and consider it an array that shows whether the i th entry is Prime or not.
  • First, make them all primes by assigning a True value to each element of the array.
  • Now, because we know the smallest prime number is 2, set the value of variable p to 2.
  • Begin by looking for all multiples of p and marking them as False.
  • Iterate until the value of p equals n, then mark all multiples as False.
  • Finally, the array members having the value True are the requisite primes.
  • For optimization purposes, the value of square of p is checked rather than p during the iteration.

2)Implementation (Static Input)

Approach:

  • Give the value of the upper limit n as static input.
  • Fill the sieve with numbers ranging from 2 to n.
  • Use a while loop that checks to see if the sieve is empty.
  • Find the smallest prime number.
  • Take that number away, then it’s multiples
  • Continue until the sieve is completely empty.
  • Exit of program.

Below is the implementation:

# Give the value of the upper limit n as static input.
numb = 20
print('The prime numbers from 1 to', numb, 'are :')
# Fill the sieve with numbers ranging from 2 to n.
sievearray = set(range(2, numb+1))
# Use a while loop that checks to see if the sieve is empty.
while sievearray:
  # Find the smallest prime number.
    primenum = min(sievearray)
    # printing the primenum
    print(primenum, end=" ")
    sievearray -= set(range(primenum, numb+1, primenum))

Output:

The prime numbers from 1 to 20 are :
2 3 5 7 11 13 17 19

Explanation:

  • Give the value of the upper limit n as static input.
  • The sieve is initialized with a set ranging from 2 to n (n+1 is not included)
  • The while loop ensures that the sieve is not empty.
  • The variable prime is initialized with the sieve’s smallest number, and the prime number is reported.
  • The sieve is then emptied of all prime number multiples.
  • Steps 4 and 5 are repeated until the sieve’s value is empty.

3)Implementation (User Input)

Approach:

  • Give the value of the upper limit n as user input using the int(input()) function.
  • Fill the sieve with numbers ranging from 2 to n.
  • Use a while loop that checks to see if the sieve is empty.
  • Find the smallest prime number.
  • Take that number away, then it’s multiples
  • Continue until the sieve is completely empty.
  • The Exit of the program.

Below is the implementation:

# Give the value of the upper limit n as user input using int(input()) function.
numb = int(input('Enter some random upper limit range = '))
print('The prime numbers from 1 to', numb, 'are :')
# Fill the sieve with numbers ranging from 2 to n.
sievearray = set(range(2, numb+1))
# Use a while loop that checks to see if the sieve is empty.
while sievearray:
  # Find the smallest prime number.
    primenum = min(sievearray)
    # printing the primenum
    print(primenum, end=" ")
    sievearray -= set(range(primenum, numb+1, primenum))

Output:

Enter some random upper limit range = 529
The prime numbers from 1 to 529 are :
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 101 103 107 109 113 127 131 137 139 
149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443
 449 457 461 463 467 479 487 491 499 503 509 521 523

This algorithm generates all primes with values less than n. It features a common improvement in that it begins enumerating the multiples of each prime I from i^2. This approach has a time complexity of O(n log log n), assuming that the array update is an O(1) operation, which is frequently the case.
Related Programs: