# Sieve of Eratosthenes with Linear time complexity

### 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.

Read more about __segmented sieve__ and try out problems __here__.

### Finding all the prime numbers using sieve

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

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 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.

2^{2} = 4. Hence, we will mark from 4 onwards.

2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |

11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

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

3^{2} = 9. Hence, we will mark from 9 onwards.

2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |

11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

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**.

5^{2} = 25. Hence, we will mark from 25 onwards.

2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |

11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

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**.

7^{2} = 49. Hence, we will mark from 49 onwards.

2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |

11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |

31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |

41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

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.

The prime no.s are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 |

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

// Code to find all the prime numbers using sieve #include <iostream> using namespace std; void primeSieveNumber(int N){ // Taking an array size of 100 int prime[100] = {0}; for(int i = 2; i * i <= N; i++){ if(prime[i] == 0){ for(int j = i * i; j <= N; j += i){ prime[j] = 1; } } } // For printing out prime no.s cout << "The prime numbers from 1 to " << N << " are: "; for(int i = 2; i <= N; i++){ if(prime[i] == 0){ cout << i << " "; } } cout << endl; } int main(){ // Take an input N to find prime numbers from 1 to N int N; cout << "Enter a number 'N' to find prime no.s from [1-N]: "; cin >> N; primeSieveNumber(N); return 0; } |

#### Output:

Enter a number 'N' to find prime no.s from [1-N]: 14 The prime no.s from 1 to 14 are: 2 3 5 7 11 13 |

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

{(N / 2) + (N / 3) + (N / 5) + (N / 7) + … + (N / P)}, where ‘P’ is the highest prime number, ‘P’ <= ‘N’ => N {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)} where {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)} is the harmonic progression of sum of primes
=> N (log (log N)) as {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)} = log(log(N)) => O(N log log N) time complexity |

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.

- First, we will check for each number if it is prime where ‘I’ lies in the range [2, N - 1].
- 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.
- We will mark the smallest prime factor of ‘i’ * ‘spf’ as ‘j’.

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

/* #include <climits> |

#### Output:

Enter a number 'N' to find prime no.s from [1-N]: 20 The smallest prime factors from 1 to 20 are: 2 3 5 7 11 13 17 19 |

#### 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)

### Frequently Asked Questions

**Explain prime factorization using the sieve of Eratosthenes.**

spf[ i ] => smallest prime factor of i while (N != 1){ print spf[N] N = N / spf[N] } |

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:

We take a number, ‘N’ = 30. The smallest prime factor of 30 is 2. Dividing ‘N’ with 2: 30 / 2 = 15 Now, dividing 15 with its spf 3: 15 / 3 = 5 Now, dividing 5 with its spf 5: 5 / 5 = 1 Therefore, the prime factors of 30 include 2, 3 and 5. |

**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

Comments

## No comments yet

## Be the first to share what you think