# Sieve of Eratosthenes with Linear time complexity

Sneha Mallik
Last Updated: May 13, 2022

### Introduction

Sieve of Eratosthenes is used to print all of the prime numbers in a given range efficiently. It is widely used in the world of competitive programming, where we try to find solutions in a better-optimized way.

Sieve of Eratosthenes is an ancient algorithm of 200+ years old, which is a simple and elegant method to find primes that are less than or equal to ‘N’ where ‘N’ is the upper range to be taken as input.

#### Note:

• A prime number has two factors: 1 and the number itself.
• 0 and 1 are not prime numbers.

### Finding all the prime numbers using sieve

Let us assume that we have numbers from 1 to 50.

Since 1 is neither composite nor prime, we will exclude 1 from the table where we have to find all the prime between the range [1, 50].

Now, we will mark all the multiples of 2 as below.

22 = 4. Hence, we will mark from 4 onwards.

Now, we will move forward to mark all the multiples of 3.

32 = 9. Hence, we will mark from 9 onwards.

Now, we will move forward, and here we notice that ‘4’ is marked. Hence, we move again to the next number to mark all the multiples of 5.

52 = 25. Hence, we will mark from 25 onwards.

Now, we will move forward, and here we notice that ‘6’ is marked. Hence, we move again to the next number to mark all the multiples of 7.

72 = 49. Hence, we will mark from 49 onwards.

Now moving on to the next number, ‘8’ is marked and its square is 64, which is more than our given range, we will stop working in the loop here. By doing this whole process, we eliminated all the non-prime numbers to get only the prime numbers.

### Code to find the prime numbers(C++)

#### Output:

Time Complexity - O(N (log(log N)) where ‘N’ is the upper bound of the input.

Space Complexity - O(N) where ‘N’ is the upper bound of the input.

To find out the prime numbers from 1 to ‘N’, the space complexity is O(N) since we are creating an array of size ‘N’. It also means that if ‘N’ is constant, then the space complexity is O(1).

Let us optimize the above code to get a linear time complexity.

### Finding prime numbers in Linear Time Complexity

There is a given upper range, ‘N’ till which we have to find prime numbers.

1. First, we will check for each number if it is prime where ‘I’ lies in the range [2, N - 1].
2. While iterating, for every prime number ‘j’ less than or equal to the smallest prime factor ‘spf’ of ‘i’, we will mark all the numbers ‘i’ * ‘spf’ as composite/not_prime.
3. We will mark the smallest prime factor of ‘i’ * ‘spf’ as ‘j’.

### Code to find prime numbers in Linear-time

#### Time Complexity

The modified sieve of Eratosthenes has a time complexity of O(N) as we cross each number at most once when we are setting its smallest prime factor. Once all the non-prime numbers are marked as false, number P * N (where ‘P’ is the smallest prime factor and N is the number) will be marked as false when we look at ‘N’.

#### Space Complexity

The space complexity is O(N) as we create an array of size ‘N’ that will take O(N) space. Therefore, overall space complexity will be O(N)

1. Explain prime factorization using the sieve of Eratosthenes.

Sieve of Eratosthenes is used to make the code run faster. Here, we will be dividing a number ‘N’ with its spf(smallest prime factor) till it reaches 1.

For example:

2. What are the advantages of using the sieve of Eratosthenes?

• It is an optimized and efficient algorithm for finding out the prime numbers in a particular range.
• It has low implementation.

3. What is meant by sieve?

Sieve is defined as the way or device used for filtering out wanted from unwanted materials. For example, we find out the prime numbers in a set of numbers and leave out the composite numbers.

### Key Takeaways

In this blog, we learned about the sieve of Eratosthenes, to find prime numbers using a sieve, the prime factorization using the sieve of Eratosthenes, and finding prime factors in linear-time with proper concepts, the code of it and its algorithm implementation.

Try problems of the sieve of Eratosthenes here on CodeStudio to understand its working algorithms. To be more confident in competitive programming concepts and data structures and algorithms, try out our Competitive Programming Course.

Credits: GIPHY

Happy Learning!

By Sneha Mallik