Table of contents

Introduction

1.1.

Example

Solution Approach

2.1.

Idea

2.2.

Algorithm

C++ Code implementation

3.1.

Complexity analysis

Frequently Asked Questions

4.1.

What is a segmented sieve?

4.2.

What is the time complexity of segmented sieve?

4.3.

What is a sieve algorithm?

Conclusion

Last Updated: Mar 27, 2024

Medium

Segmented Sieve

Q: 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.

Q: 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).

Q: 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.

Author 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

Output

2, 3, 5, 7

Explanation

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

Input

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:
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).