**Introduction**

Did you ever come across a problem where you have to find all the prime numbers in a given range? The naive approach to solve the problem would be to run a for loop for the range and check each number one by one for primeness. But this is an O(N^2) algorithm. Can you do it more efficiently?

Yes, using Sieve Algorithms. In this blog, we will discuss the **Segmented Sieve** algorithm. The **Segmented Sieve** is an optimised version of the Normal Sieve Algorithm. Unlike the normal Sieve, the **Segmented Sieve** doesn't check for all multiples of every number but only for multiples of primes calculated till some predefined limit.

Now, let's deep dive into the problem statement and see how we can solve it using a **Segmented Sieve**. The problem statement is pretty simple. You are given an integer ‘N’, where N >= 2, and you need to print all the prime numbers less than ‘N’. ‘N’ can be as large as 10^9.

**Example**

**Input**

`10 `

**Output**

`2, 3, 5, 7`

**Explanation**

2, 3, 5, 7 are the prime numbers that are less than 10.

**Input**

`20`

**Output**

`2, 3, 5, 7, 11, 13, 17, 19`

**Explanation**

primes < 20 are: 2,3,5,7,11,13,17,19

**Solution Approach **

To understand the segmented sieve concept, you need to have a clear understanding of the simple sieve concept, which is generally called as Sieve of Eratosthenes. You can read about it from __here__.

For a large value of N (>1000000), the simple sieve algorithm throws a memory limit error. To avoid this, we use the segmented sieve algorithm.

**Idea **

- Generate all prime numbers from 0 to floor(√N) using the simple sieve method.
- Partition the range [2, n) into segments of size √N.
- For every segment [l, r], mark the multiples of primes (generated in (1)) in the range [l, r] as false.
- All the numbers that are left true are primes in the given range. Append them to your final answer.

**Algorithm**

- Initialise a global array,
**primes[]**to store the prime numbers. - Define a method
**simpleSieve(int x).**This method appends all the prime numbers <= x into**primes[]**,**x = floor(√N)**. primes[], now contain all the primes <= √N. We are not going to discuss the method simpleSieve(int x) as this is a prerequisite. - Declare an empty array
**ANS**. - The idea is to partition the interval [0, N - 1] into smaller segments of size ~√N
**.**This is the point at which we optimise space complexity. This ensures that the algorithm runs for a large value of N (up to 109). - For partitioning, we run a loop L : 2 to N - 1, set low = L and high = L + √N - 1. We now have an interval
**[low, high]**of size ~√N. We now call for**segmentedSieve(low, high, ANS)**which appends all the primes in the range [low, high]. -
**segmentedSieve(low, high, ANS)**is defined as:- Initialise a local boolean array
**isPrime[]**of length**high - low + 1**as true. - For all primes
**P**in**primes[]**, we cancel out its multiples in the range [low, high], i.e. we mark them as false. The element at index 0 represents low, and the element at the last index represents high. - Iterate over isPrime[] and append (i + low) if isPrime[i] is true.

- Initialise a local boolean array