The algorithm used to calculate prime numbers

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]

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]
           ^

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

numbers = [2,3,5,7,9]
             ^  

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]  
               ^

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]
                 ^

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]

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.