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..
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.
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.
The implementation of this method is very straightforward and simple.
def prime_generator( limit ): # start off with all numbers in the bag ls = [True] * limit '''Consider point about maximum factor, mentioned in description''' # prime numbers start from 2 for i in range(2, int(math.sqrt(limit)) + 1): # iterate over all possible factors for j in range(i*2, limit, i): # and their multiples ls[j] = False # cross 'em out # 0 and 1 are not prime numbers but they are still in list, so count -2 print( "We have ", ls.count(True) - 2, " prime numbers." ) print( [i for i in range(2, limit) if ls[i]]) # print all prime numbers # test run if __name__ == '__main__': prime_generator(10)
We have 4 prime numbers. [2, 3, 5, 7]