DEV Community

Cover image for The algorithm used to calculate prime numbers
Youdiowei Eteimorde
Youdiowei Eteimorde

Posted on

The algorithm used to calculate prime numbers

#algorithms #computerscience #programming #python

Here's a coding challenge, find all the prime numbers with a range of numbers. How would you go about this problem? Could you come up with an efficient algorithm to solve this problem? Don't bother because about two thousand years ago a mathematician named Erastosenes Erathosense Eratosthenes developed an efficient algorithm for calculating prime numbers within a given range.

In this article, I will be discussing his algorithm known as The sieve of Eratosthenes.

The algorithm

We are given the number 1 through 10 and we are asked to find all prime numbers within that range.

numbers = [1,2,3,4,5,6,7,8,9,10]
Enter fullscreen mode Exit fullscreen mode

One requirement of the algorithm is that the first number in the range should be prime. We have to remove one from the list because it isn't a prime number.

numbers = [2,3,4,5,6,7,8,9,10] ^
Enter fullscreen mode Exit fullscreen mode

Take the first prime find all multiples of it and remove them from the list.

numbers = [2,3,5,7,9] ^
Enter fullscreen mode Exit fullscreen mode

Now we move to the next number which is 3. Find all multiples of it in the list and remove it.

numbers = [2,3,5,7] ^
Enter fullscreen mode Exit fullscreen mode

We move to the next prime number check for all multiples of it in the list. Since there isn't any multiple of 5 in the list we move to the next number.

numbers = [2,3,5,7] ^
Enter fullscreen mode Exit fullscreen mode

We are at the end of the list and there isn't any other number. All the numbers in the list are currently prime. That's why it is called a sieve because it filters all non-prime numbers.

Implementation

Here's a python implementation of the sieve of Eratosthenes.

# maximum number in the range n = 100 # prime numbers primes = [] # list of numbers numbers = list(range(2, n+1)) while numbers: # Assume the first number is prime  prime = numbers.pop(0) # Add prime numbers to the list  primes.append(prime) # remove all numbers divisible by the prime number  numbers = [ x for x in numbers if x % prime != 0 ] print(primes) # [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]
Enter fullscreen mode Exit fullscreen mode

Time complexity

The time complexity of the algorithm is O(n * log(log(n))). This means it is almost linear but also depends on the logarithm of the logarithm of n.

Top comments (0)