# Segmented Sieve

The segmented sieve is an algorithm used to find all prime numbers in a given range [L, R] where R - L is a large number (possibly up to 10^12 or more) and it is not feasible to use a simple sieve to find all primes in this range.

The basic idea behind the segmented sieve is to divide the range [L, R] into smaller segments and then use a simple sieve to find all primes in each segment. This way, we can efficiently find all primes in the entire range by using the primes found in the smaller segments.

The steps to implement the segmented sieve algorithm are as follows:

1. Generate all primes up to the square root of R using a simple sieve. This gives us a list of primes that we can use to sieve the smaller segments.

2. Divide the range [L, R] into smaller segments of size S. The value of S should be chosen so that it is small enough to sieve efficiently, but large enough to reduce the number of segments.

3. For each segment [i*S, (i+1)*S), where i is an integer from 0 to (R-L)/S, do the following:

a. Create a boolean array of size S to represent the numbers in the segment. Initialize all elements to true.

b. Sieve the segment using the primes generated in step 1. For each prime p, mark all multiples of p in the segment as composite (i.e., set their values to false in the boolean array).

c. Output all prime numbers in the segment (i.e., the indices in the boolean array that are still true).

1. Combine the prime numbers found in all segments to obtain the list of all primes in the range [L, R].

By using the segmented sieve algorithm, we can efficiently find all prime numbers in a large range [L, R] without having to use a lot of memory or processing power.

Here given code implementation process.

``````import java.util.ArrayList;
// Java program for
// 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
for (int j = i * i; j <= n; j += i)
{
mark[j] = false;
}
}
}
}
public void segmentedSieve(int n)
{
if (n <= 0)
{
return;
}
ArrayList < Integer > prime = new ArrayList < Integer > ();
// Get the initial prime number by given n
int limit = (int)(Math.floor(Math.sqrt(n)) + 1);
int low = limit;
int high = 2 * limit;
int value = 0;
// Container which is used to detect (√n) prime element
boolean[] mark = new boolean[limit + 1];
// Find first (√n) prime number
eratosthenesSieve(prime, limit);
// Print the initials prime number
for (int i = 0; i < prime.size(); ++i)
{
System.out.print("  " + prime.get(i));
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
// Set next (√n) prime number is valid
for (int i = 0; i <= limit; ++i)
{
mark[i] = true;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
for (int i = 0; i < prime.size(); i++)
{
value = (int)(Math.floor(low / prime.get(i)) * prime.get(i));
if (value < low)
{
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)
{
}
}``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````// Include header file
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
// C++ program for
// 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 n)
{
if (n <= 0)
{
return;
}
vector < int > prime;
// Get the initial prime number by given n
int limit = (int)(floor(sqrt(n)) + 1);
int low = limit;
int high = 2 *limit;
int value = 0;
// Container which is used to detect (√n) prime element
bool mark[limit + 1];
// Find first (√n) prime number
this->eratosthenesSieve(prime, limit);
// Print the initials prime number
for (int i = 0; i < prime.size(); ++i)
{
cout << "  " << prime.at(i);
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
// Set next (√n) prime number is valid
for (int i = 0; i <= limit; ++i)
{
mark[i] = true;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
for (int i = 0; i < prime.size(); i++)
{
value = (int)(floor(low / prime.at(i)) *prime.at(i));
if (value < low)
{
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()
{
return 0;
}``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// 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
for (int j = i * i; j <= n; j += i)
{
mark[j] = false;
}
}
}
}
public void segmentedSieve(int n)
{
if (n <= 0)
{
return;
}
List < int > prime = new List < int > ();
// Get the initial prime number by given n
int limit = (int)(Math.Floor(Math.Sqrt(n)) + 1);
int low = limit;
int high = 2 * limit;
int value = 0;
// Container which is used to detect (√n) prime element
Boolean[] mark = new Boolean[limit + 1];
// Find first (√n) prime number
this.eratosthenesSieve(prime, limit);
// Print the initials prime number
for (int i = 0; i < prime.Count; ++i)
{
Console.Write("  " + prime[i]);
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
// Set next (√n) prime number is valid
for (int i = 0; i <= limit; ++i)
{
mark[i] = true;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
for (int i = 0; i < prime.Count; i++)
{
value = (int)(Math.Floor(low / prime[i]) * prime[i]);
if (value < low)
{
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)
{
}
}``````

#### Output

``````cshap.cs(68,31): error CS0121: The call is ambiguous between the following methods or properties: `System.Math.Floor(decimal)' and `System.Math.Floor(double)'
/usr/lib/mono/4.5/mscorlib.dll (Location of the symbol related to previous error)
Compilation failed: 1 error(s), 0 warnings``````
``````// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// 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
for (int j = i * i; j <= n; j += i)
{
mark[j] = false;
}
}
}
}
public void segmentedSieve(int n)
{
if (n <= 0)
{
return;
}
List < int > prime = new List < int > ();
// Get the initial prime number by given n
int limit = (int)(Math.Floor(Math.Sqrt(n)) + 1);
int low = limit;
int high = 2 * limit;
int v = 0;
// Container which is used to detect (√n) prime element
Boolean[] mark = new Boolean[limit + 1];
// Find first (√n) prime number
this.eratosthenesSieve(prime, limit);
// Print the initials prime number
for (int i = 0; i < prime.Count; ++i)
{
Console.Write("  " + prime[i]);
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
// Set next (√n) prime number is valid
for (int i = 0; i <= limit; ++i)
{
mark[i] = true;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
for (int i = 0; i < prime.Count; i++)
{
v = (int)Math.Floor((Double)low / prime[i]) * prime[i];
if (v < low)
{
v += prime[i];
}
for (int j = v; 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)
{
}
}``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````package main
import "math"
import "fmt"
// Go program for
// Segmented Sieve
type Sieve struct {}
func getSieve() * Sieve {
var me *Sieve = &Sieve {}
return me
}
func(this Sieve) eratosthenesSieve(prime *[] int, n int) {
// Set all element as prime
var mark = make([] bool, n + 1)
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(n int) {
if n <= 0 {
return
}
var prime = make([]int,0)
// Get the initial prime number by given n
var limit int = (int)(math.Floor(math.Sqrt(float64(n))) + 1)
var low int = limit
var high int = 2 * limit
var value int = 0
// Container which is used to detect (√n) prime element
var mark = make([] bool, limit + 1)
// Find first (√n) prime number
this.eratosthenesSieve(&prime, limit)
// Print the initials prime number
for i := 0 ; i < len(prime) ; i++ {
fmt.Print("  ", prime[i])
}
// This loop displays the remaining prime number between (√n .. n)
for (low < n) {
// Set next (√n) prime number is valid
for i := 0 ; i <= limit ; i++ {
mark[i] = true
}
if high >= n {
// When next prime pair are greater than n
// Set high value to n
high = n
}
for i := 0 ; i < len(prime) ; i++ {
value = (int)(math.Floor(float64(low) / float64(prime[i])) *
float64(prime[i]))
if value < low {
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()
}``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````<?php
// Php program for
// 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(\$n)
{
if (\$n <= 0)
{
return;
}
\$prime = array();
// Get the initial prime number by given n
\$limit = (int)(floor(sqrt(\$n)) + 1);
\$low = \$limit;
\$high = 2 * \$limit;
\$value = 0;
// Container which is used to detect (√n) prime element
\$mark = array_fill(0, \$limit + 1, false);
// Find first (√n) prime number
\$this->eratosthenesSieve(\$prime, \$limit);
// Print the initials prime number
for (\$i = 0; \$i < count(\$prime); ++\$i)
{
echo("  ".\$prime[\$i]);
}
// This loop displays the remaining prime number between (√n .. n)
while (\$low < \$n)
{
// Set next (√n) prime number is valid
for (\$i = 0; \$i <= \$limit; ++\$i)
{
\$mark[\$i] = true;
}
if (\$high >= \$n)
{
// When next prime pair are greater than n
// Set high value to n
\$high = \$n;
}
for (\$i = 0; \$i < count(\$prime); \$i++)
{
\$value = (int)(floor((int)(\$low / \$prime[\$i])) * \$prime[\$i]);
if (\$value < \$low)
{
\$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()
{
}
main();``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````import math
#  Python 3 program for
#  Segmented Sieve
class Sieve :
def eratosthenesSieve(self, prime, n) :
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, n) :
if (n <= 0) :
return

prime = []
#  Get the initial prime number by given n
limit = (int)(math.floor(math.sqrt(n)) + 1)
low = limit
high = 2 * limit
value = 0
#  Container which is used to detect (√n) prime element
mark = [False] * (limit + 1)
#  Find first (√n) prime number
self.eratosthenesSieve(prime, limit)
i = 0
#  Print the initials prime number
while (i < len(prime)) :
print("  ", prime[i], end = "")
i += 1

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

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

i = 0
while (i < len(prime)) :
value = (int)(math.floor(int(low / prime[i])) * prime[i])
if (value < low) :
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() :

if __name__ == "__main__": main()``````

#### Output

``   2   3   5   7   11   13   17   19   23   29   31   37   41   43   47   53   59   61   67   71   73   79   83   89   97``
``````// Node JS program for
// 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(n)
{
if (n <= 0)
{
return;
}
var prime =  [];
// Get the initial prime number by given n
var limit = parseInt(Math.floor(Math.sqrt(n)) + 1);
var low = limit;
var high = 2 * limit;
var value = 0;
// Container which is used to detect (√n) prime element
var mark = Array(limit + 1).fill(false);
// Find first (√n) prime number
this.eratosthenesSieve(prime, limit);
// Print the initials prime number
for (var i = 0; i < prime.length; ++i)
{
process.stdout.write("  " + prime[i]);
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
// Set next (√n) prime number is valid
for (var i = 0; i <= limit; ++i)
{
mark[i] = true;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
for (var i = 0; i < prime.length; i++)
{
value = parseInt(
Math.floor(parseInt(low / prime[i])) * prime[i]
);
if (value < low)
{
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()
{
}
main();``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````#  Ruby program for
#  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(n)
if (n <= 0)
return
end

prime = []
#  Get the initial prime number by given n
limit =  (Math.sqrt(n).floor() + 1)
low = limit
high = 2 * limit
value = 0
#  Container which is used to detect (√n) prime element
mark = Array.new(limit + 1) {false}
#  Find first (√n) prime number
self.eratosthenesSieve(prime, limit)
i = 0
#  Print the initials prime number
while (i < prime.length)
print("  ", prime[i])
i += 1
end

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

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

i = 0
while (i < prime.length)
value = ((low / prime[i]).floor() * prime[i])
if (value < low)
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()
end

main()``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````import scala.collection.mutable._;
// Scala program for
// 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(n: Int): Unit = {
if (n <= 0)
{
return;
}
var prime: ArrayBuffer[Int] = new ArrayBuffer[Int]();
// Get the initial prime number by given n
var limit: Int = (Math.floor(scala.math.sqrt(n)) + 1).toInt;
var low: Int = limit;
var high: Int = 2 * limit;
var value: Int = 0;
// Container which is used to detect (√n) prime element
var mark: Array[Boolean] = Array.fill[Boolean](limit + 1)(false);
// Find first (√n) prime number
eratosthenesSieve(prime, limit);
var i: Int = 0;
// Print the initials prime number
while (i < prime.size)
{
print("  " + prime(i));
i += 1;
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
i = 0;
// Set next (√n) prime number is valid
while (i <= limit)
{
mark(i) = true;
i += 1;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
i = 0;
while (i < prime.size)
{
value = (Math.floor(low / prime(i)) * prime(i)).toInt;
if (value < low)
{
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();
}
}``````

#### Output

``  2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97``
``````import Foundation;
// Swift 4 program for
// 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(_ n: Int)
{
if (n <= 0)
{
return;
}
var prime: [Int] = [Int]();
// Get the initial prime number by given n
let limit: Int = Int((floor(Double(n).squareRoot()) + 1));
var low: Int = limit;
var high: Int = 2 * limit;
var value: Int = 0;
// Container which is used to detect (√n) prime element
var mark: [Bool] = Array(repeating: true, count: limit + 1);
// Find first (√n) prime number
self.eratosthenesSieve(&prime, limit);
var i: Int = 0;
// Print the initials prime number
while (i < prime.count)
{
print("  ", prime[i], terminator: "");
i += 1;
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
i = 0;
// Set next (√n) prime number is valid
while (i <= limit)
{
mark[i] = true;
i += 1;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
i = 0;
while (i < prime.count)
{
value = Int(floor(Double(low / prime[i]) *
Double(prime[i])));
if (value < low)
{
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()
{
}
main();``````

#### Output

``   2   3   5   7   11   13   17   19   23   29   31   37   41   43   47   53   59   61   67   71   73   79   83   89   97``
``````// Kotlin program for
// 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
var j: Int = i * i;
while (j <= n)
{
mark[j] = false;
j += i;
}
}
i += 1;
}
}
fun segmentedSieve(n: Int): Unit
{
if (n <= 0)
{
return;
}
var prime: MutableList < Int > = mutableListOf < Int > ();
// Get the initial prime number by given n
val limit: Int = (Math.floor(Math.sqrt(n.toDouble())) + 1).toInt();
var low: Int = limit;
var high: Int = 2 * limit;
var value: Int ;
// Container which is used to detect (√n) prime element
val mark: Array < Boolean > = Array(limit + 1)
{
false
};
// Find first (√n) prime number
this.eratosthenesSieve(prime, limit);
var i: Int = 0;
// Print the initials prime number
while (i < prime.size)
{
print("  " + prime[i]);
i += 1;
}
// This loop displays the remaining prime number between (√n .. n)
while (low < n)
{
i = 0;
// Set next (√n) prime number is valid
while (i <= limit)
{
mark[i] = true;
i += 1;
}
if (high >= n)
{
// When next prime pair are greater than n
// Set high value to n
high = n;
}
i = 0;
while (i < prime.size)
{
value = (Math.floor((low.toDouble() / prime[i])) *
prime[i]).toInt();
if (value < low)
{
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
{
}``````

#### Output

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

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.