Find the prime numbers between given range using segmented sieve

The segmented sieve is an optimization of the Sieve of Eratosthenes algorithm that allows us to find prime numbers in a specific range efficiently. The segmented sieve divides the range into segments and applies the sieve only to those segments, rather than the entire range.

Problem Statement

The problem is to find and print all prime numbers within a given range [s, e], where s and e are positive integers.

Idea to Solve the Problem

To solve this problem using the segmented sieve, we can follow these steps:

1. Use the regular Sieve of Eratosthenes to find all prime numbers up to the square root of the upper limit (e).

2. Initialize two pointers low and high to the starting range s and the next segment's limit (s + √e).

3. Create a boolean array mark of size limit + 1 (where limit is √e) to mark the sieve values within the current segment.

4. Loop through the prime numbers obtained from step 1. For each prime p, calculate the value value = (low / p) * p, and set it to the next multiple of p within the current segment. Mark all multiples of p as non-prime in the mark array.

5. After marking the multiples of primes in the current segment, print the prime numbers in the segment.

6. Update low and high to the next segment's limits and repeat steps 3 to 5 until the entire range [s, e] is covered.

Pseudocode

class Sieve
    method eratosthenesSieve(prime, n)
        mark = boolean array of size n + 1
        for i from 0 to n
            mark[i] = true
        mark[0] = false
        mark[1] = false
        for i from 2 to n
            if mark[i] is true
                prime.add(i)
                for j from i * i to n step i
                    mark[j] = false
    
    method segmentedSieve(s, e)
        if s < 0 or e < 2
            return
        
        prime = empty array of integers
        limit = floor(sqrt(e)) + 1
        low = s
        high = limit + s
        mark = boolean array of size limit + 1
        
        eratosthenesSieve(prime, limit)
        
        loop until low < e
            for i from 0 to limit
                mark[i] = true
            if high >= e
                high = e
            for i from 0 to prime.size
                value = floor(low / prime[i]) * prime[i]
                if value < low
                    value += prime[i]
                for j from value to high step prime[i]
                    mark[j - low] = false
            for i from low to high
                if mark[i - low] is true
                    print i
            high = high + limit
            low = low + limit
    
function main
    task = new Sieve
    task.segmentedSieve(100, 200) // Test case A
    task.segmentedSieve(999, 1200) // Test case B

Algorithm Explanation

1. The eratosthenesSieve method implements the Sieve of Eratosthenes to find all prime numbers up to n.

2. The segmentedSieve method finds and prints prime numbers within the range [s, e] using the segmented sieve algorithm:

   • It first checks if the input values are valid.
   • It initializes the variables and arrays required for the algorithm.
   • It uses the eratosthenesSieve method to find the prime numbers up to √e.
   • It then loops through the segments, marking non-prime values and printing prime numbers within each segment.

Code Solution

• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

import java.util.ArrayList;
// Java program for
// Find the prime numbers between given range using segmented sieve
public class Sieve
{
	public void eratosthenesSieve(ArrayList < Integer > prime, int n)
	{
		boolean[] mark = new boolean[n + 1];
		// Set all element as prime
		for (int i = 0; i <= n; ++i)
		{
			mark[i] = true;
		}
		mark[0] = false;
		mark[1] = false;
		for (int i = 2; i <= n; ++i)
		{
			if (mark[i] == true)
			{
				// Collect prime element
				prime.add(i);
				for (int j = i * i; j <= n; j += i)
				{
					mark[j] = false;
				}
			}
		}
	}
	public void segmentedSieve(int s, int e)
	{
		if (s < 0 || e < 2)
		{
			return;
		}
		System.out.println("\n Prime number in range of (" + s + "," + e + ")");
		ArrayList < Integer > prime = new ArrayList < Integer > ();
		// Get the initial prime number by given e
		int limit = (int)(Math.floor(Math.sqrt(e)) + 1);
		// Starting value
		int low = s;
		int high = (limit) + s;
		int value = 0;
		// Container which is used to detect (√e) prime element
		boolean[] mark = new boolean[limit + 1];
		// Find first (√e) prime number 
		eratosthenesSieve(prime, limit);
		for (int i = 0; i < prime.size(); ++i)
		{
			if (prime.get(i) >= s)
			{
				System.out.print("  " + prime.get(i));
			}
		}
		// This loop displays the remaining prime number between (√e .. e)
		while (low < e)
		{
			// Set next (√e) prime number is valid
			for (int i = 0; i <= limit; ++i)
			{
				mark[i] = true;
			}
			if (high >= e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				high = e;
			}
			for (int i = 0; i < prime.size(); i++)
			{
				value = (int)(Math.floor(low / prime.get(i)) * prime.get(i));
				if (value < low)
				{
					// Add current prime value 
					value += prime.get(i);
				}
				for (int j = value; j < high; j += prime.get(i))
				{
					// Set mutiple is non prime
					mark[j - low] = false;
				}
			}
			// Display prime elements
			for (int i = low; i < high; i++)
			{
				if (mark[i - low] == true)
				{
					System.out.print("  " + i);
				}
			}
			// Update of all multiple of value is non prime
			high = high + limit;
			low = low + limit;
		}
	}
	public static void main(String[] args)
	{
		Sieve task = new Sieve();
		// Test
		task.segmentedSieve(100, 200);
		task.segmentedSieve(999, 1200);
	}
}

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

// Include header file
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
// C++ program for
// Find the prime numbers between given range using segmented sieve
class Sieve
{
	public: void eratosthenesSieve(vector < int > &prime, int n)
	{
		bool mark[n + 1];
		// Set all element as prime
		for (int i = 0; i <= n; ++i)
		{
			mark[i] = true;
		}
		mark[0] = false;
		mark[1] = false;
		for (int i = 2; i <= n; ++i)
		{
			if (mark[i] == true)
			{
				// Collect prime element
				prime.push_back(i);
				for (int j = i *i; j <= n; j += i)
				{
					mark[j] = false;
				}
			}
		}
	}
	void segmentedSieve(int s, int e)
	{
		if (s < 0 || e < 2)
		{
			return;
		}
		cout << "\n Prime number in range of (" 
             << s << "," << e << ")" << endl;
		vector < int > prime;
		// Get the initial prime number by given e
		int limit = (int)(floor(sqrt(e)) + 1);
		// Starting value
		int low = s;
		int high = limit + s;
		int value = 0;
		// Container which is used to detect (√e) prime element
		bool mark[limit + 1];
		// Find first (√e) prime number 
		this->eratosthenesSieve(prime, limit);
		for (int i = 0; i < prime.size(); ++i)
		{
			if (prime.at(i) >= s)
			{
				cout << "  " << prime.at(i);
			}
		}
		// This loop displays the remaining prime number between (√e .. e)
		while (low < e)
		{
			// Set next (√e) prime number is valid
			for (int i = 0; i <= limit; ++i)
			{
				mark[i] = true;
			}
			if (high >= e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				high = e;
			}
			for (int i = 0; i < prime.size(); i++)
			{
				value = (int)(floor(low / prime.at(i)) * prime.at(i));
				if (value < low)
				{
					// Add current prime value 
					value += prime.at(i);
				}
				for (int j = value; j < high; j += prime.at(i))
				{
					// Set mutiple is non prime
					mark[j - low] = false;
				}
			}
			// Display prime elements
			for (int i = low; i < high; i++)
			{
				if (mark[i - low] == true)
				{
					cout << "  " << i;
				}
			}
			// Update of all multiple of value is non prime
			high = high + limit;
			low = low + limit;
		}
	}
};
int main()
{
	Sieve *task = new Sieve();
	// Test
	task->segmentedSieve(100, 200);
	task->segmentedSieve(999, 1200);
	return 0;
}

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Find the prime numbers between given range using segmented sieve
public class Sieve
{
	public void eratosthenesSieve(List < int > prime, int n)
	{
		Boolean[] mark = new Boolean[n + 1];
		// Set all element as prime
		for (int i = 0; i <= n; ++i)
		{
			mark[i] = true;
		}
		mark[0] = false;
		mark[1] = false;
		for (int i = 2; i <= n; ++i)
		{
			if (mark[i] == true)
			{
				// Collect prime element
				prime.Add(i);
				for (int j = i * i; j <= n; j += i)
				{
					mark[j] = false;
				}
			}
		}
	}
	public void segmentedSieve(int s, int e)
	{
		if (s < 0 || e < 2)
		{
			return;
		}
		Console.WriteLine("\n Prime number in range of (" + s + "," + e + ")");
		List < int > prime = new List < int > ();
		// Get the initial prime number by given e
		int limit = (int)(Math.Floor(Math.Sqrt(e)) + 1);
		// Starting value
		int low = s;
		int high = (limit) + s;
		int value = 0;
		// Container which is used to detect (√e) prime element
		Boolean[] mark = new Boolean[limit + 1];
		// Find first (√e) prime number 
		this.eratosthenesSieve(prime, limit);
		for (int i = 0; i < prime.Count; ++i)
		{
			if (prime[i] >= s)
			{
				Console.Write("  " + prime[i]);
			}
		}
		// This loop displays the remaining prime number between (√e .. e)
		while (low < e)
		{
			// Set next (√e) prime number is valid
			for (int i = 0; i <= limit; ++i)
			{
				mark[i] = true;
			}
			if (high >= e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				high = e;
			}
			for (int i = 0; i < prime.Count; i++)
			{
				value = (int)(Math.Floor((double)(low / prime[i])) * prime[i]);
				if (value < low)
				{
					// Add current prime value 
					value += prime[i];
				}
				for (int j = value; j < high; j += prime[i])
				{
					// Set mutiple is non prime
					mark[j - low] = false;
				}
			}
			// Display prime elements
			for (int i = low; i < high; i++)
			{
				if (mark[i - low] == true)
				{
					Console.Write("  " + i);
				}
			}
			// Update of all multiple of value is non prime
			high = high + limit;
			low = low + limit;
		}
	}
	public static void Main(String[] args)
	{
		Sieve task = new Sieve();
		// Test
		task.segmentedSieve(100, 200);
		task.segmentedSieve(999, 1200);
	}
}

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

package main
import "math"
import "fmt"
// Go program for
// Find the prime numbers between given range using segmented sieve
type Sieve struct {}
func getSieve() * Sieve {
	var me *Sieve = &Sieve {}
	return me
}
func(this Sieve) eratosthenesSieve(prime *[]int, n int) {
	var mark = make([] bool, n + 1)
	// Set all element as prime
	for i := 0 ; i <= n ; i++ {
		mark[i] = true
	}
	mark[0] = false
	mark[1] = false
	for i := 2 ; i <= n ; i++ {
		if mark[i] == true {
			// Collect prime element
			*prime = append(*prime, i)
			for j := i * i ; j <= n ; j += i {
				mark[j] = false
			}
		}
	}
}
func(this Sieve) segmentedSieve(s, e int) {
	if s < 0 || e < 2 {
		return
	}
	fmt.Println("\n Prime number in range of (", s, ",", e, ")")
	var prime = make([]int ,0)
	// Get the initial prime number by given e
	var limit int = (int)(math.Floor(math.Sqrt(float64(e))) + 1)
	// Starting value
	var low int = s
	var high int = (limit) + s
	var value int = 0
	// Container which is used to detect (√e) prime element
	var mark = make([] bool, limit + 1)
	// Find first (√e) prime number 
	this.eratosthenesSieve(&prime, limit)
	for i := 0 ; i < len(prime) ; i++ {
		if prime[i] >= s {
			fmt.Print("  ", prime[i])
		}
	}
	// This loop displays the remaining prime number between (√e .. e)
	for (low < e) {
		// Set next (√e) prime number is valid
		for i := 0 ; i <= limit ; i++ {
			mark[i] = true
		}
		if high >= e {
			// When next prime pair are greater than e
			// Set high value to e
			high = e
		}
		for i := 0 ; i < len(prime) ; i++ {
			value = (int)(math.Floor(float64(low / prime[i])) * float64(prime[i]))
			if value < low {
				// Add current prime value 
				value += prime[i]
			}
			for j := value ; j < high ; j += prime[i] {
				// Set mutiple is non prime
				mark[j - low] = false
			}
		}
		// Display prime elements
		for i := low ; i < high ; i++ {
			if mark[i - low] == true {
				fmt.Print("  ", i)
			}
		}
		// Update of all multiple of value is non prime
		high = high + limit
		low = low + limit
	}
}
func main() {
	var task * Sieve = getSieve()
	// Test
	task.segmentedSieve(100, 200)
	task.segmentedSieve(999, 1200)
}

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

<?php
// Php program for
// Find the prime numbers between given range using segmented sieve
class Sieve
{
	public	function eratosthenesSieve(&$prime, $n)
	{
      	// Set all element as prime
		$mark = array_fill(0, $n + 1, true);
		$mark[0] = false;
		$mark[1] = false;
		for ($i = 2; $i <= $n; ++$i)
		{
			if ($mark[$i] == true)
			{
				// Collect prime element
				$prime[] = $i;
				for ($j = $i * $i; $j <= $n; $j += $i)
				{
					$mark[$j] = false;
				}
			}
		}
	}
	public	function segmentedSieve($s, $e)
	{
		if ($s < 0 || $e < 2)
		{
			return;
		}
		echo("\n Prime number in range of (".$s.
			",".$e.
			")".
			"\n");
		$prime = array();
		// Get the initial prime number by given e
		$limit = (int)(floor(sqrt($e)) + 1);
		// Starting value
		$low = $s;
		$high = ($limit) + $s;
		$value = 0;
		// Container which is used to detect (√e) prime element
		$mark = array_fill(0, $limit + 1, false);
		// Find first (√e) prime number 
		$this->eratosthenesSieve($prime, $limit);
		for ($i = 0; $i < count($prime); ++$i)
		{
			if ($prime[$i] >= $s)
			{
				echo("  ".$prime[$i]);
			}
		}
		// This loop displays the remaining prime number between (√e .. e)
		while ($low < $e)
		{
			// Set next (√e) prime number is valid
			for ($i = 0; $i <= $limit; ++$i)
			{
				$mark[$i] = true;
			}
			if ($high >= $e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				$high = $e;
			}
			for ($i = 0; $i < count($prime); $i++)
			{
				$value = (int)(floor((int)($low / $prime[$i])) * $prime[$i]);
				if ($value < $low)
				{
					// Add current prime value 
					$value += $prime[$i];
				}
				for ($j = $value; $j < $high; $j += $prime[$i])
				{
					// Set mutiple is non prime
					$mark[$j - $low] = false;
				}
			}
			// Display prime elements
			for ($i = $low; $i < $high; $i++)
			{
				if ($mark[$i - $low] == true)
				{
					echo("  ".$i);
				}
			}
			// Update of all multiple of value is non prime
			$high = $high + $limit;
			$low = $low + $limit;
		}
	}
}

function main()
{
	$task = new Sieve();
	// Test
	$task->segmentedSieve(100, 200);
	$task->segmentedSieve(999, 1200);
}
main();

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

// Node JS program for
// Find the prime numbers between given range using segmented sieve
class Sieve
{
	eratosthenesSieve(prime, n)
	{
		// Set all element as prime
		var mark = Array(n + 1).fill(true);
		mark[0] = false;
		mark[1] = false;
		for (var i = 2; i <= n; ++i)
		{
			if (mark[i] == true)
			{
				// Collect prime element
				prime.push(i);
				for (var j = i * i; j <= n; j += i)
				{
					mark[j] = false;
				}
			}
		}
	}
	segmentedSieve(s, e)
	{
		if (s < 0 || e < 2)
		{
			return;
		}
		console.log("\n Prime number in range of (" + 
                    s + "," + e + ")");
		var prime = [];
		// Get the initial prime number by given e
		var limit = parseInt(Math.floor(Math.sqrt(e)) + 1);
		// Starting value
		var low = s;
		var high = (limit) + s;
		var value = 0;
		// Container which is used to detect (√e) prime element
		var mark = Array(limit + 1).fill(false);
		// Find first (√e) prime number 
		this.eratosthenesSieve(prime, limit);
		for (var i = 0; i < prime.length; ++i)
		{
			if (prime[i] >= s)
			{
				process.stdout.write("  " + prime[i]);
			}
		}
		// This loop displays the remaining prime number between (√e .. e)
		while (low < e)
		{
			// Set next (√e) prime number is valid
			for (var i = 0; i <= limit; ++i)
			{
				mark[i] = true;
			}
			if (high >= e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				high = e;
			}
			for (var i = 0; i < prime.length; i++)
			{
				value = parseInt(
                  Math.floor(parseInt(low / prime[i])) * prime[i]);
				if (value < low)
				{
					// Add current prime value 
					value += prime[i];
				}
				for (var j = value; j < high; j += prime[i])
				{
					// Set mutiple is non prime
					mark[j - low] = false;
				}
			}
			// Display prime elements
			for (var i = low; i < high; i++)
			{
				if (mark[i - low] == true)
				{
					process.stdout.write("  " + i);
				}
			}
			// Update of all multiple of value is non prime
			high = high + limit;
			low = low + limit;
		}
	}
}

function main()
{
	var task = new Sieve();
	// Test
	task.segmentedSieve(100, 200);
	task.segmentedSieve(999, 1200);
}
main();

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

import math
#  Python 3 program for
#  Find the prime numbers between given range using segmented sieve
class Sieve :
	def eratosthenesSieve(self, prime, n) :
		#  Set all element as prime
		mark = [True] * (n + 1)
		mark[0] = False
		mark[1] = False
		i = 2
		while (i <= n) :
			if (mark[i] == True) :
				#  Collect prime element
				prime.append(i)
				j = i * i
				while (j <= n) :
					mark[j] = False
					j += i
				
			
			i += 1
		
	
	def segmentedSieve(self, s, e) :
		if (s < 0 or e < 2) :
			return
		
		print("\n Prime number in range of (", s ,",", e ,")")
		prime = []
		#  Get the initial prime number by given e
		limit = (int)(math.floor(math.sqrt(e)) + 1)
		#  Starting value
		low = s
		high = (limit) + s
		value = 0
		#  Container which is used to detect (√e) prime element
		mark = [False] * (limit + 1)
		#  Find first (√e) prime number 
		self.eratosthenesSieve(prime, limit)
		i = 0
		while (i < len(prime)) :
			if (prime[i] >= s) :
				print("  ", prime[i], end = "")
			
			i += 1
		
		#  This loop displays the remaining prime number between (√e .. e)
		while (low < e) :
			i = 0
			#  Set next (√e) prime number is valid
			while (i <= limit) :
				mark[i] = True
				i += 1
			
			if (high >= e) :
				#  When next prime pair are greater than e
				#  Set high value to e
				high = e
			
			i = 0
			while (i < len(prime)) :
				value = (int)(math.floor(int(low / prime[i])) * prime[i])
				if (value < low) :
					#  Add current prime value 
					value += prime[i]
				
				j = value
				while (j < high) :
					#  Set mutiple is non prime
					mark[j - low] = False
					j += prime[i]
				
				i += 1
			
			i = low
			#  Display prime elements
			while (i < high) :
				if (mark[i - low] == True) :
					print("  ", i, end = "")
				
				i += 1
			
			#  Update of all multiple of value is non prime
			high = high + limit
			low = low + limit
		
	

def main() :
	task = Sieve()
	#  Test
	task.segmentedSieve(100, 200)
	task.segmentedSieve(999, 1200)

if __name__ == "__main__": main()

 Prime number in range of ( 100 , 200 )
   101   103   107   109   113   127   131   137   139   149   151   157   163   167   173   179   181   191   193   197   199
 Prime number in range of ( 999 , 1200 )
   1009   1013   1019   1021   1031   1033   1039   1049   1051   1061   1063   1069   1087   1091   1093   1097   1103   1109   1117   1123   1129   1151   1153   1163   1171   1181   1187   1193

#  Ruby program for
#  Find the prime numbers between given range using segmented sieve
class Sieve 
	def eratosthenesSieve(prime, n) 
		#  Set all element as prime
		mark = Array.new(n + 1) {true}
		mark[0] = false
		mark[1] = false
		i = 2
		while (i <= n) 
			if (mark[i] == true) 
				#  Collect prime element
				prime.push(i)
				j = i * i
				while (j <= n) 
					mark[j] = false
					j += i
				end

			end

			i += 1
		end

	end

	def segmentedSieve(s, e) 
		if (s < 0 || e < 2) 
			return
		end

		print("\n Prime number in range of (", s ,",", e ,")", "\n")
		prime = []
		#  Get the initial prime number by given e
		limit = (Math.sqrt(e).floor() + 1)
		#  Starting value
		low = s
		high = (limit) + s
		value = 0
		#  Container which is used to detect (√e) prime element
		mark = Array.new(limit + 1) {false}
		#  Find first (√e) prime number 
		self.eratosthenesSieve(prime, limit)
		i = 0
		while (i < prime.length) 
			if (prime[i] >= s) 
				print("  ", prime[i])
			end

			i += 1
		end

		#  This loop displays the remaining prime number between (√e .. e)
		while (low < e) 
			i = 0
			#  Set next (√e) prime number is valid
			while (i <= limit) 
				mark[i] = true
				i += 1
			end

			if (high >= e) 
				#  When next prime pair are greater than e
				#  Set high value to e
				high = e
			end

			i = 0
			while (i < prime.length) 
				value = (low / prime[i].floor() * prime[i])
				if (value < low) 
					#  Add current prime value 
					value += prime[i]
				end

				j = value
				while (j < high) 
					#  Set mutiple is non prime
					mark[j - low] = false
					j += prime[i]
				end

				i += 1
			end

			i = low
			#  Display prime elements
			while (i < high) 
				if (mark[i - low] == true) 
					print("  ", i)
				end

				i += 1
			end

			#  Update of all multiple of value is non prime
			high = high + limit
			low = low + limit
		end

	end

end

def main() 
	task = Sieve.new()
	#  Test
	task.segmentedSieve(100, 200)
	task.segmentedSieve(999, 1200)
end

main()

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

import scala.collection.mutable._;
// Scala program for
// Find the prime numbers between given range using segmented sieve
class Sieve()
{
	def eratosthenesSieve(prime: ArrayBuffer[Int], n: Int): Unit = {
		// Set all element as prime
		var mark: Array[Boolean] = Array.fill[Boolean](n + 1)(true);
		mark(0) = false;
		mark(1) = false;
		var i: Int = 2;
		while (i <= n)
		{
			if (mark(i) == true)
			{
				// Collect prime element
				prime += i;
				var j: Int = i * i;
				while (j <= n)
				{
					mark(j) = false;
					j += i;
				}
			}
			i += 1;
		}
	}
	def segmentedSieve(s: Int, e: Int): Unit = {
		if (s < 0 || e < 2)
		{
			return;
		}
		println("\n Prime number in range of (" + s + "," + e + ")");
		var prime: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		// Get the initial prime number by given e
		var limit: Int = (Math.floor(scala.math.sqrt(e)) + 1).toInt;
		// Starting value
		var low: Int = s;
		var high: Int = (limit) + s;
		var value: Int = 0;
		// Container which is used to detect (√e) prime element
		var mark: Array[Boolean] = Array.fill[Boolean](limit + 1)(false);
		// Find first (√e) prime number 
		eratosthenesSieve(prime, limit);
		var i: Int = 0;
		while (i < prime.size)
		{
			if (prime(i) >= s)
			{
				print("  " + prime(i));
			}
			i += 1;
		}
		// This loop displays the remaining prime number between (√e .. e)
		while (low < e)
		{
			i = 0;
			// Set next (√e) prime number is valid
			while (i <= limit)
			{
				mark(i) = true;
				i += 1;
			}
			if (high >= e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				high = e;
			}
			i = 0;
			while (i < prime.size)
			{
				value = (Math.floor(low / prime(i)) * prime(i)).toInt;
				if (value < low)
				{
					// Add current prime value 
					value += prime(i);
				}
				var j: Int = value;
				while (j < high)
				{
					// Set mutiple is non prime
					mark(j - low) = false;
					j += prime(i);
				}
				i += 1;
			}
			i = low;
			// Display prime elements
			while (i < high)
			{
				if (mark(i - low) == true)
				{
					print("  " + i);
				}
				i += 1;
			}
			// Update of all multiple of value is non prime
			high = high + limit;
			low = low + limit;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Sieve = new Sieve();
		// Test
		task.segmentedSieve(100, 200);
		task.segmentedSieve(999, 1200);
	}
}

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

import Foundation;
// Swift 4 program for
// Find the prime numbers between given range using segmented sieve
class Sieve
{
	func eratosthenesSieve(_ prime: inout[Int], _ n: Int)
	{
		// Set all element as prime
		var mark: [Bool] = Array(repeating: true, count: n + 1);
		mark[0] = false;
		mark[1] = false;
		var i: Int = 2;
		while (i <= n)
		{
			if (mark[i] == true)
			{
				// Collect prime element
				prime.append(i);
				var j: Int = i * i;
				while (j <= n)
				{
					mark[j] = false;
					j += i;
				}
			}
			i += 1;
		}
	}
	func segmentedSieve(_ s: Int, _ e: Int)
	{
		if (s < 0 || e < 2)
		{
			return;
		}
		print("\n Prime number in range of (", s ,",", e ,")");
		var prime: [Int] = [Int]();
		// Get the initial prime number by given e
		let limit: Int = Int((floor(Double(e).squareRoot()) + 1));
		// Starting value
		var low: Int = s;
		var high: Int = (limit) + s;
		var value: Int = 0;
		// Container which is used to detect (√e) prime element
		var mark: [Bool] = Array(repeating: false, count: limit + 1);
		// Find first (√e) prime number 
		self.eratosthenesSieve(&prime, limit);
		var i: Int = 0;
		while (i < prime.count)
		{
			if (prime[i] >= s)
			{
				print("  ", prime[i], terminator: "");
			}
			i += 1;
		}
		// This loop displays the remaining prime number between (√e .. e)
		while (low < e)
		{
			i = 0;
			// Set next (√e) prime number is valid
			while (i <= limit)
			{
				mark[i] = true;
				i += 1;
			}
			if (high >= e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				high = e;
			}
			i = 0;
			while (i < prime.count)
			{
				value = Int((floor(Double(low / prime[i])) * Double(prime[i])));
				if (value < low)
				{
					// Add current prime value 
					value += prime[i];
				}
				var j: Int = value;
				while (j < high)
				{
					// Set mutiple is non prime
					mark[j - low] = false;
					j += prime[i];
				}
				i += 1;
			}
			i = low;
			// Display prime elements
			while (i < high)
			{
				if (mark[i - low] == true)
				{
					print("  ", i, terminator: "");
				}
				i += 1;
			}
			// Update of all multiple of value is non prime
			high = high + limit;
			low = low + limit;
		}
	}
}
func main()
{
	let task: Sieve = Sieve();
	// Test
	task.segmentedSieve(100, 200);
	task.segmentedSieve(999, 1200);
}
main();

 Prime number in range of ( 100 , 200 )
   101   103   107   109   113   127   131   137   139   149   151   157   163   167   173   179   181   191   193   197   199
 Prime number in range of ( 999 , 1200 )
   1009   1013   1019   1021   1031   1033   1039   1049   1051   1061   1063   1069   1087   1091   1093   1097   1103   1109   1117   1123   1129   1151   1153   1163   1171   1181   1187   1193

// Kotlin program for
// Find the prime numbers between given range using segmented sieve
class Sieve
{
	fun eratosthenesSieve(prime: MutableList < Int >  , n : Int): Unit
	{
		// Set all element as prime
		val mark: Array < Boolean > = Array(n + 1)
		{
			true
		};
		mark[0] = false;
		mark[1] = false;
		var i: Int = 2;
		while (i <= n)
		{
			if (mark[i] == true)
			{
				// Collect prime element
				prime.add(i);
				var j: Int = i * i;
				while (j <= n)
				{
					mark[j] = false;
					j += i;
				}
			}
			i += 1;
		}
	}
	fun segmentedSieve(s: Int, e: Int): Unit
	{
		if (s < 0 || e < 2)
		{
			return;
		}
		println("\n Prime number in range of (" + s + "," + e + ")");
		var prime: MutableList < Int > = mutableListOf < Int > ();
		// Get the initial prime number by given e
		val limit: Int = (Math.floor(Math.sqrt(e.toDouble())) + 1.0).toInt();
		// Starting value
		var low: Int = s;
		var high: Int = (limit) + s;
		var value: Int ;
		// Container which is used to detect (√e) prime element
		val mark: Array < Boolean > = Array(limit + 1)
		{
			false
		};
		// Find first (√e) prime number 
		this.eratosthenesSieve(prime, limit);
		var i: Int = 0;
		while (i < prime.size)
		{
			if (prime[i] >= s)
			{
				print("  " + prime[i]);
			}
			i += 1;
		}
		// This loop displays the remaining prime number between (√e .. e)
		while (low < e)
		{
			i = 0;
			// Set next (√e) prime number is valid
			while (i <= limit)
			{
				mark[i] = true;
				i += 1;
			}
			if (high >= e)
			{
				// When next prime pair are greater than e
				// Set high value to e
				high = e;
			}
			i = 0;
			while (i < prime.size)
			{
				value = (Math.floor(
                  (low / prime[i]).toDouble()
                ) * prime[i]).toInt();
				if (value < low)
				{
					// Add current prime value 
					value += prime[i];
				}
				var j: Int = value;
				while (j < high)
				{
					// Set mutiple is non prime
					mark[j - low] = false;
					j += prime[i];
				}
				i += 1;
			}
			i = low;
			// Display prime elements
			while (i < high)
			{
				if (mark[i - low] == true)
				{
					print("  " + i);
				}
				i += 1;
			}
			// Update of all multiple of value is non prime
			high = high + limit;
			low = low + limit;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Sieve = Sieve();
	// Test
	task.segmentedSieve(100, 200);
	task.segmentedSieve(999, 1200);
}

 Prime number in range of (100,200)
  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199
 Prime number in range of (999,1200)
  1009  1013  1019  1021  1031  1033  1039  1049  1051  1061  1063  1069  1087  1091  1093  1097  1103  1109  1117  1123  1129  1151  1153  1163  1171  1181  1187  1193

Time Complexity

• Generating prime numbers using the Sieve of Eratosthenes has a time complexity of O(n log log n).
• The segmented sieve algorithm has a time complexity of O((e - s + 1) * log log e), where e is the upper limit and s is the lower limit of the range.