Segmentiertes Sieb
Geben Sie bei einer gegebenen Zahl n alle Primzahlen kleiner als n aus. Wenn die angegebene Zahl beispielsweise 10 ist, geben Sie 2, 3, 5, 7 aus.
Ein naiver Ansatz besteht darin, eine Schleife von 0 bis n-1 zu durchlaufen und jede Zahl auf Primzahl zu überprüfen. Ein besserer Ansatz ist die Verwendung von Simple Sieve of Eratosthenes .
C
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
void simpleSieve(int limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
bool mark[limit];
for(int i = 0; i<limit; i++) {
mark[i] = true;
}
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p=2; p<limit; p++)
if (mark[p] == true)
cout << p << " ";
}
Java
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
static void simpleSieve(int limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
boolean []mark = new boolean[limit];
Arrays.fill(mark, true);
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (int p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p = 2; p < limit; p++)
if (mark[p] == true)
System.out.print(p + " ");
}
// This code is contributed by rutvik_56.
Python3
# This functions finds all primes smaller than 'limit' # using simple sieve of eratosthenes. def simpleSieve(limit): # Create a boolean array "mark[0..limit-1]" and # initialize all entries of it as true. A value # in mark[p] will finally be false if 'p' is Not # a prime, else true. mark = [True for i in range(limit)] # One by one traverse all numbers so that their # multiples can be marked as composite. for p in range(p * p, limit - 1, 1): # If p is not changed, then it is a prime if (mark[p] == True): # Update all multiples of p for i in range(p * p, limit - 1, p): mark[i] = False # Print all prime numbers and store them in prime for p in range(2, limit - 1, 1): if (mark[p] == True): print(p, end=" ") # This code is contributed by Dharanendra L V.
C#
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
static void simpleSieve(int limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
bool []mark = new bool[limit];
Array.Fill(mark, true);
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (int p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p = 2; p < limit; p++)
if (mark[p] == true)
Console.Write(p + " ");
}
// This code is contributed by pratham76.
Javascript
<script>
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
function simpleSieve(limit)
{
// Create a boolean array "mark[0..limit-1]" and
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
var mark = Array(limit).fill(true);
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (p = 2; p < limit; p++)
if (mark[p] == true)
document.write(p + " ");
}
// This code is contributed by todaysgaurav
</script>
Probleme mit Simple Sieve:
Das Sieb von Eratosthenes sieht gut aus, aber bedenken Sie die Situation, wenn n groß ist, das Simple Sieve steht vor den folgenden Problemen.
- Ein Array der Größe Θ(n) passt möglicherweise nicht in den Speicher
- Das einfache Sieb ist auch für etwas größere n nicht cachefreundlich. Der Algorithmus durchläuft das Array ohne Bezugsort
Segmentiertes Sieb
Die Idee eines segmentierten Siebs besteht darin, den Bereich [0..n-1] in verschiedene Segmente zu unterteilen und in allen Segmenten nacheinander Primzahlen zu berechnen. Dieser Algorithmus verwendet zuerst Simple Sieve, um Primzahlen zu finden, die kleiner oder gleich √(n) sind. Unten sind die Schritte aufgeführt, die beim segmentierten Sieb verwendet werden.
- Verwenden Sie Simple Sieve, um alle Primzahlen bis zur Quadratwurzel von 'n' zu finden, und speichern Sie diese Primzahlen in einem Array „prime[]“. Speichern Sie die gefundenen Primzahlen in einem Array 'prime[]'.
- Wir brauchen alle Primzahlen im Bereich [0..n-1]. Wir unterteilen diesen Bereich in verschiedene Segmente, sodass die Größe jedes Segments höchstens √n beträgt
- Tun Sie Folgendes für jedes Segment [low..high]
- Erstellen Sie eine Array-Markierung [high-low+1]. Hier benötigen wir nur O(x) Raum, wobei x eine Anzahl von Elementen in einem gegebenen Bereich ist.
- Iteriere durch alle in Schritt 1 gefundenen Primzahlen. Markiere für jede Primzahl ihre Vielfachen im gegebenen Bereich [low..high].
In Simple Sieve benötigten wir O(n)-Platz, was für große n möglicherweise nicht machbar ist. Hier benötigen wir O(√n)-Raum und verarbeiten kleinere Bereiche gleichzeitig (Referenzort)
Unten ist die Implementierung der obigen Idee.
C++
// C++ program to print print all primes smaller than
// n using segmented sieve
#include <bits/stdc++.h>
using namespace std;
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes. It also stores
// found primes in vector prime[]
void simpleSieve(int limit, vector<int> &prime)
{
// Create a boolean array "mark[0..n-1]" and initialize
// all entries of it as true. A value in mark[p] will
// finally be false if 'p' is Not a prime, else true.
vector<bool> mark(limit + 1, true);
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p=2; p<limit; p++)
{
if (mark[p] == true)
{
prime.push_back(p);
cout << p << " ";
}
}
}
// Prints all prime numbers smaller than 'n'
void segmentedSieve(int n)
{
// Compute all primes smaller than or equal
// to square root of n using simple sieve
int limit = floor(sqrt(n))+1;
vector<int> prime;
prime.reserve(limit);
simpleSieve(limit, prime);
// Divide the range [0..n-1] in different segments
// We have chosen segment size as sqrt(n).
int low = limit;
int high = 2*limit;
// While all segments of range [0..n-1] are not processed,
// process one segment at a time
while (low < n)
{
if (high >= n)
high = n;
// To mark primes in current range. A value in mark[i]
// will finally be false if 'i-low' is Not a prime,
// else true.
bool mark[limit+1];
memset(mark, true, sizeof(mark));
// Use the found primes by simpleSieve() to find
// primes in current range
for (int i = 0; i < prime.size(); i++)
{
// Find the minimum number in [low..high] that is
// a multiple of prime[i] (divisible by prime[i])
// For example, if low is 31 and prime[i] is 3,
// we start with 33.
int loLim = floor(low/prime[i]) * prime[i];
if (loLim < low)
loLim += prime[i];
/* Mark multiples of prime[i] in [low..high]:
We are marking j - low for j, i.e. each number
in range [low, high] is mapped to [0, high-low]
so if range is [50, 100] marking 50 corresponds
to marking 0, marking 51 corresponds to 1 and
so on. In this way we need to allocate space only
for range */
for (int j=loLim; j<high; j+=prime[i])
mark[j-low] = false;
}
// Numbers which are not marked as false are prime
for (int i = low; i<high; i++)
if (mark[i - low] == true)
cout << i << " ";
// Update low and high for next segment
low = low + limit;
high = high + limit;
}
}
// Driver program to test above function
int main()
{
int n = 100000;
cout << "Primes smaller than " << n << ":n";
segmentedSieve(n);
return 0;
}
Java
// Java program to print print all primes smaller than
// n using segmented sieve
import java.util.Vector;
import static java.lang.Math.sqrt;
import static java.lang.Math.floor;
class Test
{
// This methid finds all primes smaller than 'limit'
// using simple sieve of eratosthenes. It also stores
// found primes in vector prime[]
static void simpleSieve(int limit, Vector<Integer> prime)
{
// Create a boolean array "mark[0..n-1]" and initialize
// all entries of it as true. A value in mark[p] will
// finally be false if 'p' is Not a prime, else true.
boolean mark[] = new boolean[limit+1];
for (int i = 0; i < mark.length; i++)
mark[i] = true;
for (int p=2; p*p<limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i=p*p; i<limit; i+=p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p=2; p<limit; p++)
{
if (mark[p] == true)
{
prime.add(p);
System.out.print(p + " ");
}
}
}
// Prints all prime numbers smaller than 'n'
static void segmentedSieve(int n)
{
// Compute all primes smaller than or equal
// to square root of n using simple sieve
int limit = (int) (floor(sqrt(n))+1);
Vector<Integer> prime = new Vector<>();
simpleSieve(limit, prime);
// Divide the range [0..n-1] in different segments
// We have chosen segment size as sqrt(n).
int low = limit;
int high = 2*limit;
// While all segments of range [0..n-1] are not processed,
// process one segment at a time
while (low < n)
{
if (high >= n)
high = n;
// To mark primes in current range. A value in mark[i]
// will finally be false if 'i-low' is Not a prime,
// else true.
boolean mark[] = new boolean[limit+1];
for (int i = 0; i < mark.length; i++)
mark[i] = true;
// Use the found primes by simpleSieve() to find
// primes in current range
for (int i = 0; i < prime.size(); i++)
{
// Find the minimum number in [low..high] that is
// a multiple of prime.get(i) (divisible by prime.get(i))
// For example, if low is 31 and prime.get(i) is 3,
// we start with 33.
int loLim = (int) (floor(low/prime.get(i)) * prime.get(i));
if (loLim < low)
loLim += prime.get(i);
/* Mark multiples of prime.get(i) in [low..high]:
We are marking j - low for j, i.e. each number
in range [low, high] is mapped to [0, high-low]
so if range is [50, 100] marking 50 corresponds
to marking 0, marking 51 corresponds to 1 and
so on. In this way we need to allocate space only
for range */
for (int j=loLim; j<high; j+=prime.get(i))
mark[j-low] = false;
}
// Numbers which are not marked as false are prime
for (int i = low; i<high; i++)
if (mark[i - low] == true)
System.out.print(i + " ");
// Update low and high for next segment
low = low + limit;
high = high + limit;
}
}
// Driver method
public static void main(String args[])
{
int n = 100;
System.out.println("Primes smaller than " + n + ":");
segmentedSieve(n);
}
}
Python3
# Python3 program to print all primes
# smaller than n, using segmented sieve
import math
prime = []
# This method finds all primes
# smaller than 'limit' using
# simple sieve of eratosthenes.
# It also stores found primes in list prime
def simpleSieve(limit):
# Create a boolean list "mark[0..n-1]" and
# initialize all entries of it as True.
# A value in mark[p] will finally be False
# if 'p' is Not a prime, else True.
mark = [True for i in range(limit + 1)]
p = 2
while (p * p <= limit):
# If p is not changed, then it is a prime
if (mark[p] == True):
# Update all multiples of p
for i in range(p * p, limit + 1, p):
mark[i] = False
p += 1
# Print all prime numbers
# and store them in prime
for p in range(2, limit):
if mark[p]:
prime.append(p)
print(p,end = " ")
# Prints all prime numbers smaller than 'n'
def segmentedSieve(n):
# Compute all primes smaller than or equal
# to square root of n using simple sieve
limit = int(math.floor(math.sqrt(n)) + 1)
simpleSieve(limit)
# Divide the range [0..n-1] in different segments
# We have chosen segment size as sqrt(n).
low = limit
high = limit * 2
# While all segments of range [0..n-1] are not processed,
# process one segment at a time
while low < n:
if high >= n:
high = n
# To mark primes in current range. A value in mark[i]
# will finally be False if 'i-low' is Not a prime,
# else True.
mark = [True for i in range(limit + 1)]
# Use the found primes by simpleSieve()
# to find primes in current range
for i in range(len(prime)):
# Find the minimum number in [low..high]
# that is a multiple of prime[i]
# (divisible by prime[i])
# For example, if low is 31 and prime[i] is 3,
# we start with 33.
loLim = int(math.floor(low / prime[i]) *
prime[i])
if loLim < low:
loLim += prime[i]
# Mark multiples of prime[i] in [low..high]:
# We are marking j - low for j, i.e. each number
# in range [low, high] is mapped to [0, high-low]
# so if range is [50, 100] marking 50 corresponds
# to marking 0, marking 51 corresponds to 1 and
# so on. In this way we need to allocate space
# only for range
for j in range(loLim, high, prime[i]):
mark[j - low] = False
# Numbers which are not marked as False are prime
for i in range(low, high):
if mark[i - low]:
print(i, end = " ")
# Update low and high for next segment
low = low + limit
high = high + limit
# Driver Code
n = 100
print("Primes smaller than", n, ":")
segmentedSieve(100)
# This code is contributed by bhavyadeep
C#
// C# program to print print
// all primes smaller than
// n using segmented sieve
using System;
using System.Collections;
class GFG
{
// This methid finds all primes
// smaller than 'limit' using simple
// sieve of eratosthenes. It also stores
// found primes in vector prime[]
static void simpleSieve(int limit,
ArrayList prime)
{
// Create a boolean array "mark[0..n-1]"
// and initialize all entries of it as
// true. A value in mark[p] will finally be
// false if 'p' is Not a prime, else true.
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
for (int p = 2; p * p < limit; p++)
{
// If p is not changed, then it is a prime
if (mark[p] == true)
{
// Update all multiples of p
for (int i = p * p; i < limit; i += p)
mark[i] = false;
}
}
// Print all prime numbers and store them in prime
for (int p = 2; p < limit; p++)
{
if (mark[p] == true)
{
prime.Add(p);
Console.Write(p + " ");
}
}
}
// Prints all prime numbers smaller than 'n'
static void segmentedSieve(int n)
{
// Compute all primes smaller than or equal
// to square root of n using simple sieve
int limit = (int) (Math.Floor(Math.Sqrt(n)) + 1);
ArrayList prime = new ArrayList();
simpleSieve(limit, prime);
// Divide the range [0..n-1] in
// different segments We have chosen
// segment size as sqrt(n).
int low = limit;
int high = 2*limit;
// While all segments of range
// [0..n-1] are not processed,
// process one segment at a time
while (low < n)
{
if (high >= n)
high = n;
// To mark primes in current range.
// A value in mark[i] will finally
// be false if 'i-low' is Not a prime,
// else true.
bool[] mark = new bool[limit + 1];
for (int i = 0; i < mark.Length; i++)
mark[i] = true;
// Use the found primes by
// simpleSieve() to find
// primes in current range
for (int i = 0; i < prime.Count; i++)
{
// Find the minimum number in
// [low..high] that is a multiple
// of prime.get(i) (divisible by
// prime.get(i)) For example,
// if low is 31 and prime.get(i)
// is 3, we start with 33.
int loLim = ((int)Math.Floor((double)(low /
(int)prime[i])) * (int)prime[i]);
if (loLim < low)
loLim += (int)prime[i];
/* Mark multiples of prime.get(i) in [low..high]:
We are marking j - low for j, i.e. each number
in range [low, high] is mapped to [0, high-low]
so if range is [50, 100] marking 50 corresponds
to marking 0, marking 51 corresponds to 1 and
so on. In this way we need to allocate space only
for range */
for (int j = loLim; j < high; j += (int)prime[i])
mark[j-low] = false;
}
// Numbers which are not marked as false are prime
for (int i = low; i < high; i++)
if (mark[i - low] == true)
Console.Write(i + " ");
// Update low and high for next segment
low = low + limit;
high = high + limit;
}
}
// Driver code
static void Main()
{
int n = 100;
Console.WriteLine("Primes smaller than " + n + ":");
segmentedSieve(n);
}
}
// This code is contributed by mits
Ausgabe:
Primes smaller than 100: 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
Beachten Sie, dass die Zeitkomplexität (oder eine Anzahl von Operationen) von Segmented Sieve mit Simple Sieve identisch ist . Es hat Vorteile für große 'n', da es eine bessere Referenzlokalität hat, wodurch ein besseres Caching durch die CPU ermöglicht wird und auch weniger Speicherplatz benötigt wird.
Dieser Artikel wurde von Utkarsh Trivedi beigesteuert. Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .