C++ Segmented Sieve (Print Primes In a Range)














































C++ Segmented Sieve (Print Primes In a Range)



Segmented Sieve (Print Primes in a Range)


Given a range [low, high], print all primes in this range? For example, if the given range is [10, 20], then output is 11, 13, 17, 19.

Naive approach is to run a loop from low to high and check each number for primeness. 
A Better Approach is to precalculate primes up to the maximum limit using Sieve of Eratosthenes, then print all prime numbers in range. 
The above approach looks good, but consider the input range [50000, 55000]. the above Sieve approach would precalculate primes from 2 to 50100. This causes a waste of memory as well as time. Below is the Segmented Sieve based approach.

Segmented Sieve (Background) 
Below are basic steps to get an idea of how Segmented Sieve works 

  1. Use Simple Sieve to find all primes up to a predefined limit (square root of high is used in below code) and store these primes in an array prime[] Basically we call Simple Sieve for a limit and we not only find prime numbers, but also puts them in a separate array prime[].
  2. Create an array mark[high-low+1]. Here we need only O(n) space where n is number of elements in given range.
  3. Iterate through all primes found in step 1. For every prime, mark its multiples in given range [low..high].

So unlike simple sieve, we don't check for all multiples of every number smaller than square root of high, we only check for multiples of primes found in step 1. And we don't need O(high) space, we need O(sqrt(high) + n) space.
Below is the implementation of above idea.

// C++ program to
// print all primes in a range
// using concept of Segmented Sieve
#include <bits/stdc++.h>
using namespace std;
// This functions finds all
// primes smaller than limit
// using simple sieve of eratosthenes.
// It stores found
// primes in vector prime[]
void simpleSieve(int limit, vector<int>& prime)
{
bool mark[limit + 1];
memset(mark, false, sizeof(mark));
for (int i = 2; i*i <= limit; ++i)
{
if (mark[i] == false)
{
// If not marked yet, then its a prime
prime.push_back(i);
for (int j = i; j <= limit; j += i)
mark[j] = true;
}
}
}
// Finds all prime numbers
// in given range using
// segmented sieve
void primesInRange(int low, int high)
{
// Compute all primes smaller or equal to
// square root of high using simple sieve
int limit = floor(sqrt(high)) + 1;
vector<int> prime;
simpleSieve(limit, prime);
// Count of elements in given range
int n = high - low + 1;
// Declaring boolean only for [low, high]
bool mark[n + 1];
memset(mark, false, sizeof(mark));
// Use the found primes by
// simpleSieve() to find
// primes in given range
for (int i = 0; i < prime.size(); i++)
{
// Find the minimum number
// in [low..high] that is
// a multiple of prime[i]
// (divisible by prime[i])
int loLim = floor(low / prime[i]) * prime[i];
if (loLim < low)
loLim += prime[i];
if(loLim==prime[i])
loLim += prime[i];
/* Mark multiples of prime[i]
in [low..high]:
We are marking j - low
for j, i.e. each number
in range [low, high] is
mapped to [0, high - low]
so if range is [50, 100]
marking 50 corresponds
to marking 0, marking
51 corresponds to 1 and
so on.Also if the current j
is prime don't mark
it as true.In this way we need
to allocate space only
for range */
for (int j = loLim; j <= high; j += prime[i])
if(j != prime[i])
mark[j - low] = true;
}
// Numbers which are not marked
// in range, are prime
for (int i = low; i <= high; i++)
if (!mark[i - low])
cout << i << " ";
}
// Driver Code
int main()
{
int low = 10, high = 20;
primesInRange(low, high);
return 0;
}
Output
11  13  15  17  19  

Segmented Sieve (What if high value of range is too high and range is also big) 
Consider a situation where given high value is so high that neither sqrt(high) nor O(high-low+1) can fit in memory. How to find prims in range. For this situation, we run step 1 (Simple Sieve) only for a limit that can fit in memory. Then we divide given range in different segments. For every segment, we run step 2 and 3 considering low and high as end points of current segment. We add primes of current segment to prime[] before running the next segment.


More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 163 0
C++ Sieve Of Erastosthenes 136 0
C++ Gold Mine Problem 295 0
C++ Merge K Sorted Arrays 117 0
C++ K Centers Problem 240 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 286 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 121 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 92 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 200 0
C++ Smallest window with all characters in string 94 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 87 0
C++ Minimum characters added at front of string in palindrome conversion 70 0
C++ Number of Bracket Reversals needed to make expression Balanced 72 0
C++ String to Palindrome with Append Function 83 0
C++ WildCard pattern matching 76 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 83 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 114 0
C++ String Matching(KMP Algorithm) 141 0
C++ Remove Duplicates From String 111 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 87 0
C++ Problem On Disjoint Data Structures 95 0
C++ Disjoint Data Structures Part3 79 0
Disjoint Data Structures Part2 91 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 291 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 526 0
C++ Greedy Approach Maximum height Pyramid 329 1
C++ Greedy Approach String lexicographically largest subsequence 247 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 334 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 349 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 745 1
C++ Greedy Approach-Egyptian Fractions 640 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2

Comments