Sieve of Eratosthenes’ method of finding prime numbers: a python code

Sieve of Eratosthenes is one of the most popular method of finding prime numbers less than or equal to the given number. This method basically works by first listing out all the natural number less than or equal to number of interest (n) then it gradually discard numbers that are divisible by smaller undiscarded numbers. It works with process of elimination, that is to say, if a given number is not divisible by number below itself (except for 1) then it is a prime number, basically a definition of prime number.

Note: I may add more theory to it later, meantime if you have any question on the code and or method, you can reach out to me via comment in the post. For now, please find theory part here: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I am going to use set instead of list or array for the code because of their ability to operate faster.

#Sieve of Eratosthenes method to find prime numbers

def stevyEr(n):
  primeList = set()
  notPrimeList = set()
  for j in range(2, n+1):
    if j not in notPrimeList:
     new_val = {j*k for k in range(j, n) if j*k<=n}
     notPrimeList = notPrimeList.union(new_val)
     primeList.add(j)
  return primeList

# Example Code Execution
print(stevyEr(100))

#Output:
{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}

Thought provoking: if you see in the list of prime numbers, you will notice that there are more prime numbers in smaller interval when the values are smaller. For example, there are three prime numbers between 0 and 5, where as there are only six prime numbers between 0 and 16.

Lets see how does this trend keep up as the number increases. For that I wrote down a follow up code to see the trend of number of prime numbers present in between zero and that number.

import matplotlib.pyplot as plt
noOfPrime = []
xAxis = []
for i in range (2, 1000, 10):
  noOfPrime.append(len(stevyEr(i))/i)
  xAxis.append(i)

plt.plot(xAxis, noOfPrime)
plt.ylabel ('ratio of number of primes and total natural number')
plt.xlabel('number of natural numbers')
plt.show()

Here is the output:

It is interesting to see, as the number increases, the quantity of prime number decreases asymptotically which is fun to see and meantime as obvious as well because with larger number there are increased number of factors.