Skip to main content

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
				prime.add(i);
				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)
				{
					// 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();
		task.segmentedSieve(100);
	}
}

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)
				{
					// 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();
	task->segmentedSieve(100);
	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
				prime.Add(i);
				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)
				{
					// 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();
		task.segmentedSieve(100);
	}
}

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
                prime.Add(i);
                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)
                {
                    // Add current prime value 
                    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)
    {
        Sieve task = new Sieve();
        task.segmentedSieve(100);
    }
}

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 {
				// 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()
	task.segmentedSieve(100)
}

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)
				{
					// 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();
	$task->segmentedSieve(100);
}
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) :
					#  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()
	task.segmentedSieve(100)

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)
				{
					// 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();
	task.segmentedSieve(100);
}
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) 
					#  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()
	task.segmentedSieve(100)
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)
				{
					// 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();
		task.segmentedSieve(100);
	}
}

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)
				{
					// 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();
	task.segmentedSieve(100);
}
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
				prime.add(i);
				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)
				{
					// 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();
	task.segmentedSieve(100);
}

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
Last updated on by Kalkicode




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.

New Comment