Segmented Sieve Print Primes In A Range In C++

In this post, we explore the concept of Segmented Sieve (Printing Prime Numbers within a Range) in C++. The Segmented Sieve represents an enhanced iteration of the Standard Sieve Algorithm. In contrast to the standard Sieve method that identifies all the multiples of each number, the Segmented Sieve identifies multiples of a selected set of primes up to a specified threshold.

The Segmented Sieve technique is applicable to handling a wide range of large numbers and is particularly useful for prime number identification. This method builds upon the Sieve of Eratosthenes by dividing the range into smaller segments and leveraging precomputed prime numbers to detect composite numbers within these segments.

This tutorial will delve into the Segmented Sieve technique, illustrating its functionality and utilization in C++.

Below are the steps to the Segmented Sieve Algorithm.

• ✅ Define the Range: Decide which interval [low, high] of the numbers we are going to look for prime numbers in.
• ✅ Sieve of Eratosthenes: During the execution step, we should apply the Sieve of Eratosthenes algorithm to identify the prime numbers not bigger than the square root of high. These primes can help in crossing out non-prime numbers within the range.
• ✅ Segment Initialization: Initialize a boolean array for the segment [low, high] with all numbers set to true because at first all the number is considered to be prime.
• ✅ Mark Non-Primes: In regard to each of the primes found in step 2 above, cross out the multiples of the prime in the segment.
• ✅ Output the Primes: The numbers which are marked as prime numbers are the output in the range.

Example:

Let's consider a scenario to demonstrate the Segmented Sieve algorithm (Displaying Prime Numbers within a Specified Range) using C++.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
// Function to find the Sieve of Eratosthenes operation
vector<int> simpleSieveNum(int lmt) {
    vector<bool> mark_Sieves(lmt + 1, true);
    vector<int> primeNum;

    for (int p = 2; p * p <= lmt; p++) {
        if (mark_Sieves[p]) {
            for (int i = p * p; i <= lmt; i += p)
                mark_Sieves[i] = false;
        }
    }
    for (int p = 2; p <= lmt; p++) {
        if (mark_Sieves[p])
            primeNum.push_back(p);
    }
    return primeNum;
}

// function to print the prime numbers in the given range
void segmentedSieve_Num(int low, int high) {
    int lmt = floor(sqrt(high)) + 1;
    vector<int> prime_Num = simpleSieveNum(lmt);
    
    vector<bool> isPrimeNum(high - low + 1, true);

    for (int i = 0; i < prime_Num.size(); i++) {
        // Finding the minimum number in the range
        int minMultipleNum = max(prime_Num[i] * prime_Num[i], (low + prime_Num[i] - 1) / prime_Num[i] * prime_Num[i]);

        // Marking the prime numbers
        for (int j = minMultipleNum; j <= high; j += prime_Num[i]) {
            isPrimeNum[j - low] = false;
        }
    }

    // return of prime numbers in the given range
    for (int i = low; i <= high; i++) {
        if (isPrimeNum[i - low] && i > 1) {
            cout << i << " ";
        }
    }
    cout << endl;
}

// Main function
int main() {
    int low, high;
    cout << "Enter the range (low high): ";
    cin >> low >> high;

    segmentedSieve_Num(low, high);
    return 0;
}

Output:

Enter the range (low high): 10 100
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Explanation:

This C++ software utilizes the Segmented Sieve technique to compute and exhibit the prime numbers within the specified range of [low, high]. Initially, the program defines the simpleSieveNum function, which operates using the Sieve of Eratosthenes principle to identify primes equal to or less than the square root of high. Within this function, a boolean array named markSieves is structured to monitor the primality of numbers, with non-prime numbers being designated as false. The prime numbers are stored in a vector array titled primeNum. Subsequently, the segmentedSieveNum function is invoked, which establishes a boolean array named isPrimeNum for the designated range of [low, high] and initializes all indices to true by default.

The primes produced by the simpleSieveNum function are employed to identify the initial smallest multiple of each prime within the specified range. Subsequently, the multiples and following values in the isPrimeNum array are marked as 0. The script iterates through each element in the isPrimeNum array, displaying the prime numbers and negating them with 1. Finally, the program prompts the user for input and invokes the segmented sieve function, which segments the provided range and identifies all prime numbers within that range.

Advantages:

The segmented sieve can be used with a large range of numbers[L, R] when the upper limit R can be in billions. It is still memory efficient because it does not require storing or processing of numbers up to R.

• ✅ Reduces Space Complexity: Compared with the sieve using all numbers up to R, the segmented sieve only necessitates storing the numbers between L and R inclusive, which saves space.
• ✅ Reuse of Primes: The simple Sieve of Eratosthenes is used to precompute primes up to Root R, and in order to mark all multiples in the range [L,R], these primes are reused.
• ✅ Divide-and-Conquer Approach: Large data inputs are also easily manageable because the algorithm breaks the problem into small parts.
• ✅ Parallelizable: Since different segments can be computed separately from one another, the algorithm was designed for parallel processing and multi-threading.
• ✅ Handles Arbitrary Ranges: Note that the algorithm enables the identification of primes between the range L to R, almost forgetting that the lower range L is always 1. This flexibility is very important for problems that may require a certain range of accuracy.

Disadvantages:

Several disadvantages of Segmented Sieve are as follows:

• ✅ Complex Implementation: In contrast to the Sieve of Eratosthenes, segmented sieve is harder to code because of special cases and scope calculations.
• ✅ Initial Overhead: Computing the primes up to Root R involves an initial overhead, which may not be efficient for small ranges or scenarios where R is relatively small.
• ✅ Memory Usage for Large Ranges: When calculating the primes up to Root R there is certainly some overhead, which means it is used least for small ranges or when R is small. There exists a need to manage edge structures and range calculations appropriately.
• ✅ Not Optimal for Small Ranges: For smaller ranges, the constant cost of generating primes up to Root R might be counterproductive to the gain achieved by segmentation for simpler forms of methods.

Conclusion:

In summary, the Segmented Sieve Algorithm is positioned as a cost-effective solution for identifying prime numbers within a specified range. Compared to the basic sieve method, the segmented sieve proves more efficient for larger ranges, although it demands significant memory allocation for the boolean array representing [L, R], especially when R extends into the billions. As indicated earlier, there is no necessity to retain all prime numbers simultaneously, only those falling within the range of L and R. This is achieved through precomputing primes via the Sieve of Eratosthenes technique, which is well-suited for handling substantial datasets. Furthermore, the algorithm performs optimally when divided into smaller, more manageable sub-problems.

Nevertheless, the segmented sieve method presents significant complexity and upfront expenses, making it less suitable for smaller ranges and uncomplicated issues. This technique is particularly valuable for scenarios demanding the generation of prime numbers across extensive intervals, offering optimized performance in terms of both speed and memory allocation.