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:
-
Use the regular Sieve of Eratosthenes to find all prime numbers up to the square root of the upper limit (e).
-
Initialize two pointers
low
andhigh
to the starting range s and the next segment's limit (s + √e). -
Create a boolean array
mark
of sizelimit + 1
(wherelimit
is √e) to mark the sieve values within the current segment. -
Loop through the prime numbers obtained from step 1. For each prime
p
, calculate the valuevalue = (low / p) * p
, and set it to the next multiple ofp
within the current segment. Mark all multiples ofp
as non-prime in themark
array. -
After marking the multiples of primes in the current segment, print the prime numbers in the segment.
-
Update
low
andhigh
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
-
The
eratosthenesSieve
method implements the Sieve of Eratosthenes to find all prime numbers up ton
. -
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
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);
}
}
Output
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;
}
Output
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);
}
}
Output
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)
}
Output
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();
Output
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();
Output
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()
Output
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()
Output
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);
}
}
Output
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();
Output
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);
}
Output
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.
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