Sieb des Eratosthenes
Geben Sie bei einer gegebenen Zahl n alle Primzahlen kleiner oder gleich n aus. Es ist auch gegeben, dass n eine kleine Zahl ist.
Beispiel:
Eingabe: n = 10
Ausgabe: 2 3 5 7Eingabe: n = 20
Ausgabe: 2 3 5 7 11 13 17 19
Das Sieb von Eratosthenes ist eine der effizientesten Methoden, um alle Primzahlen kleiner als n zu finden, wenn n kleiner als etwa 10 Millionen ist (Ref Wiki ).
Wenn der Algorithmus endet, sind alle Zahlen in der Liste, die nicht markiert sind, Primzahlen.
Erklärung mit Beispiel:
Nehmen wir ein Beispiel, wenn n = 50 ist. Wir müssen also alle Primzahlen kleiner oder gleich 50 drucken.
Wir erstellen eine Liste aller Zahlen von 2 bis 50.
Gemäß dem Algorithmus markieren wir alle Zahlen, die durch 2 teilbar und größer oder gleich dem Quadrat davon sind.
Jetzt gehen wir zu unserer nächsten unmarkierten Zahl 3 und markieren alle Zahlen, die Vielfache von 3 sind und größer oder gleich dem Quadrat davon sind.
Wir bewegen uns zu unserer nächsten nicht markierten Zahl 5 und markieren alle Vielfachen von 5 und sind größer oder gleich dem Quadrat davon.
Wir setzen diesen Prozess fort und unsere Abschlusstabelle wird wie folgt aussehen:
Die Primzahlen sind also die unmarkierten: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Danke an Krishan Kumar für die obige Erklärung.
Implementierung:
Es folgt die Implementierung des obigen Algorithmus. In der folgenden Implementierung wird ein boolesches Array arr[] der Größe n verwendet, um Vielfache von Primzahlen zu markieren.
C++
// C++ program to print all primes // smaller than or equal to // n using Sieve of Eratosthenes #include <bits/stdc++.h> using namespace std; void SieveOfEratosthenes(int n) { // Create a boolean array // "prime[0..n]" and initialize // all entries it as true. // A value in prime[i] will // finally be false if i is // Not a prime, else true. bool prime[n + 1]; memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples // of p greater than or // equal to the square of it // numbers which are multiple // of p and are less than p^2 // are already been marked. for (int i = p * p; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (int p = 2; p <= n; p++) if (prime[p]) cout << p << " "; } // Driver Code int main() { int n = 30; cout << "Following are the prime numbers smaller " << " than or equal to " << n << endl; SieveOfEratosthenes(n); return 0; }
Java
// Java program to print all // primes smaller than or equal to // n using Sieve of Eratosthenes class SieveOfEratosthenes { void sieveOfEratosthenes(int n) { // Create a boolean array // "prime[0..n]" and // initialize all entries // it as true. A value in // prime[i] will finally be // false if i is Not a // prime, else true. boolean prime[] = new boolean[n + 1]; for (int i = 0; i <= n; i++) prime[i] = true; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a // prime if (prime[p] == true) { // Update all multiples of p for (int i = p * p; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (int i = 2; i <= n; i++) { if (prime[i] == true) System.out.print(i + " "); } } // Driver Code public static void main(String args[]) { int n = 30; System.out.print( "Following are the prime numbers "); System.out.println("smaller than or equal to " + n); SieveOfEratosthenes g = new SieveOfEratosthenes(); g.sieveOfEratosthenes(n); } } // This code has been contributed by Amit Khandelwal.
Python
# Python program to print all # primes smaller than or equal to # n using Sieve of Eratosthenes def SieveOfEratosthenes(n): # Create a boolean array # "prime[0..n]" and initialize # all entries it as true. # A value in prime[i] will # finally be false if i is # Not a prime, else true. prime = [True for i in range(n+1)] p = 2 while (p * p <= n): # If prime[p] is not # changed, then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * p, n+1, p): prime[i] = False p += 1 # Print all prime numbers for p in range(2, n+1): if prime[p]: print p, # Driver code if __name__ == '__main__': n = 30 print "Following are the prime numbers smaller", print "than or equal to", n SieveOfEratosthenes(n)
C#
// C# program to print all primes // smaller than or equal to n // using Sieve of Eratosthenes using System; namespace prime { public class GFG { public static void SieveOfEratosthenes(int n) { // Create a boolean array // "prime[0..n]" and // initialize all entries // it as true. A value in // prime[i] will finally be // false if i is Not a // prime, else true. bool[] prime = new bool[n + 1]; for (int i = 0; i < n; i++) prime[i] = true; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * p; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (int i = 2; i <= n; i++) { if (prime[i] == true) Console.Write(i + " "); } } // Driver Code public static void Main() { int n = 30; Console.WriteLine( "Following are the prime numbers"); Console.WriteLine("smaller than or equal to " + n); SieveOfEratosthenes(n); } } } // This code is contributed by Sam007.
PHP
<?php // php program to print all primes smaller // than or equal to n using Sieve of // Eratosthenes function SieveOfEratosthenes($n) { // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be // false if i is Not a prime, else true. $prime = array_fill(0, $n+1, true); for ($p = 2; $p*$p <= $n; $p++) { // If prime[p] is not changed, // then it is a prime if ($prime[$p] == true) { // Update all multiples of p for ($i = $p*$p; $i <= $n; $i += $p) $prime[$i] = false; } } // Print all prime numbers for ($p = 2; $p <= $n; $p++) if ($prime[$p]) echo $p." "; } // Driver Code $n = 30; echo "Following are the prime numbers " ."smaller than or equal to " .$n."\n" ; SieveOfEratosthenes($n); // This code is contributed by mits ?>
Javascript
<script> // javascript program to print all // primes smaller than or equal to // n using Sieve of Eratosthenes function sieveOfEratosthenes(n) { // Create a boolean array // "prime[0..n]" and // initialize all entries // it as true. A value in // prime[i] will finally be // false if i is Not a // prime, else true. prime = Array.from({length: n+1}, (_, i) => true); for (p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a // prime if (prime[p] == true) { // Update all multiples of p for (i = p * p; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (i = 2; i <= n; i++) { if (prime[i] == true) document.write(i + " "); } } // Driver Code var n = 30; document.write( "Following are the prime numbers "); document.write("smaller than or equal to " + n+"<br>"); sieveOfEratosthenes(n); // This code is contributed by 29AjayKumar </script>
Es folgen die Primzahlen kleiner oder gleich 30 2 3 5 7 11 13 17 19 23 29
Zeitkomplexität : O(n*log(log(n)))
Sie können auch gerne sehen:
- Wie ist die Zeitkomplexität von Sieve of Eratosthenes ist n*log(log(n))?
- Segmentiertes Sieb .
- Sieb des Eratosthenes in 0(n) Zeitkomplexität
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 .