1.
Introduction
1.1.
Example
2.
Solution Approach
2.1.
Idea
2.2.
Algorithm
3.
C++ Code implementation
3.1.
Complexity analysis
4.
4.1.
What is a segmented sieve?
4.2.
What is the time complexity of segmented sieve?
4.3.
What is a sieve algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Segmented Sieve

Ayush Prakash

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

1. Initialise a global array, primes[] to store the prime numbers.
2. 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.
3. Declare an empty array ANS
4. The idea is to partition the interval [0, N - 1] into smaller segments of size ~√NThis is the point at which we optimise space complexity. This ensures that the algorithm runs for a large value of N (up to 109).
5. 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].
6. segmentedSieve(low, high, ANS) is defined as:
1. Initialise a local boolean array isPrime[] of length high - low + 1 as true.
2. 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.
3. Iterate over isPrime[] and append (i + low) if isPrime[i] is true.

## C++ Code implementation

``````#include <bits/stdc++.h>
using namespace std;

// To hold the prime numbers <= sqrt(n)
vector<int> primes;

// Get all the primes <= x
// x = sqrt(n)
void simpleSieve(int x)
{
vector<bool> isPrime(x + 1, true);

/*
Making 0 and 1 as false since
they are not prime
*/
isPrime[0] = false;
isPrime[1] = false;

// Sieve for filtering out the primes <= x
for (int i = 2; i * i <= x; i++)
{
if (isPrime[i])
{
// Cancelling out all the multiples of i
for (int m = i * i; m <= x; m += i)
{
isPrime[m] = false;
}
}
}

// Add the primes into primes[]
for (int i = 2; i <= x; i++)
{
if (isPrime[i])
{
primes.push_back(i);
}
}
}

void segmentedSieve(int low, int high, vector<int> &ans)
{
vector<int> isPrime(high - low + 1, true);

// Looping over all the primes
for (int p : primes)
{

// Choosing the first multiple of p >= low
int s = low / p * p;
if (s < low)
{
s += p;
}

// Cancelling out the factors of p
for (int i = s; i <= high; i += p)
{
isPrime[i - low] = false;
}
}

// Append primes in range [low, high] in ans
for (int i = 0; i < isPrime.size(); i++)
{
if (isPrime[i])
{
ans.push_back(i + low);
}
}
}

int main()
{
primes.clear();

// Take input
int n;
cin >> n;

// Get all primes <= sqrt(n)
simpleSieve((int)floor(sqrt(n)));

vector<int> ans;

/*
divide the range [2, n-1] into
smaller segments of size sqrt(n),
use segmentedSieve to find all the
primes in the range [l, r] and append
to ans
*/

// For every segment, we call segmentedSieve()
int updateVal = floor(sqrt(n));
for (int l = 2; l < n; l += updateVal)
{
int r = min(l + updateVal - 1, n - 1);
segmentedSieve(l, r, ans);
}

// Printing all the primes < n
for (int p : ans)
{
cout << p << " ";
}
cout << endl;
}``````

Output:

``````100
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ``````

### Complexity analysis

Time complexity : O(N * log(logN))

The number of operations performed in simlpeSieve and segmentedSieve is the same. Therefore, time complexity of segmented sieve = time complexity of simpleSieve = O(N * log(logN)). To have a better understanding, please read about the simpleSieve method.

Space complexity: Θ(√N)

Array ‘primes[]’ is using Θ(√N) space, size of every segment we are passing in segmented Sieve method is  Θ(√N). For calculating all the primes using the simple Sieve method, we require Θ(√N) space. Everywhere in the implementation, we have used either constant space or Θ(√N) space. Hence taking the higher-order term, the space complexity = Θ(√N).

### What is a segmented sieve?

The Segmented Sieve is an optimised version of the normal Sieve Algorithm. Unlike the normal Sieve algorithm, the Segmented Sieve does not check for all multiples of every number but only for multiples of primes calculated till some predefined limit.

### What is the time complexity of segmented sieve?

The time complexity of the Segmented Sieve algorithm is O(n), where n is the total number of elements present inside the given range. The space complexity of the Segmented Sieve algorithm is the same as the time complexity, i.e., O(n).

### What is a sieve algorithm?

A Sieve algorithm is an optimised algorithm used to find the prime numbers in a given range. The naive method solves the problem in O(N^2) time complexity, and a Sieve algorithm does it in O(n*log(logn)), which can further reduce to O(n) using Segmented Sieve.

## Conclusion

This blog discussed a very popular number theory problem, segmented sieve. We also analysed the space and time complexity and found out that both the segmented sieve and the simple sieve algorithms have the same time complexity, but the segmented sieve algorithm takes less space and hence it is used over the simple sieve when the value of N is large. We saw the CPP implementation of the approach as well.