Today we’ll do some time traveling and MATH, yay! So, this is about finding/listing prime numbers. Eratosthenes’ Sieve is an ancient method for finding prime numbers, and it is fast! Let’s find out..

Eratosthenes’ Sieve

The Sieve of Eratosthenes is one of the most popular methods for finding and counting prime numbers within a range. The reason for its popularity is, as you can guess, its speed.

Working

This algorithm is based on the theory of prime numbers and factors. The algorithms iterates over all the possible factors of the given range (limit), and crosses out their multiples, which means those cannot be prime numbers. After all the factors have been scanned, the numbers still left are prime numbers. Its time complexity is O( log( log n ) ) operations.

Note: A number cannot have a factor greater than its square root, so avoid redundant iterating.

Code

The implementation of this method is very straightforward and simple.

defprime_generator(limit):# start off with all numbers in the bagls=[True]*limit'''Consider point about maximum factor, mentioned in description'''# prime numbers start from 2foriinrange(2,int(math.sqrt(limit))+1):# iterate over all possible factorsforjinrange(i*2,limit,i):# and their multiplesls[j]=False# cross 'em out# 0 and 1 are not prime numbers but they are still in list, so count -2print("We have ",ls.count(True)-2," prime numbers.")print([iforiinrange(2,limit)ifls[i]])# print all prime numbers# test runif__name__=='__main__':prime_generator(10)