Primzahlen spielen bei modernen Verschlüsselungsmethoden eine wichtige Rolle, weswegen es gerade in der Informatik wichtig zu wissen ist, wie man Primzahlen finden kann.
In diesem Tutorial wollen wir einen der gängigsten Algorithmen verwenden um alle Primzahlen bis zu einer definierten Grenze zu finden. Dazu verwenden wir das sogenannte „Sieb des Eratosthenes“ (Siehe Wikipedia).
Zur Erinnerung: Primzahlen sind alle natürlichen Zahlen, die ausschließlich durch 1 und sich selbst teilbar sind. Eine Primzahl hat also genau zwei Teiler. Folglich ist jede Zahl, die ein Vielfaches einer Primzahl ist, keine Primzahl. Das „Sieb des Eratosthenes“ verwendet diese Eigenschaft um aus einer Liste alle Nicht-Primzahlen zu streichen und nur die übrig zu lassen, die Primzahlen sind.
Vorgehensweise nach dem Sieb des Eratosthenes
- Erstelle eine Liste mit allen Zahlen von 2 bis zur Grenze (max)
- Die kleinste unmarkierte Zahl ist eine Primzahl (–> im ersten Schritt also die 2)
- Markiere alle Vielfachen dieser Zahl in der Liste als „keine Primzahl“
- Wiederhole Schritt 2. und 3. so lange, bis das Quadrat der gefunden Primzahl größer als die Grenze ist.
Beispiel – Primzahlen bis 20:
Schritt 1:
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Schritt 2.1 (Primzahl rot markiert):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Schritt 3.1 (Vielfache grün markiert):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Schritt 2.2 (3 ist eine Primzahl):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Schritt 3.2 (markiere alle Vielfachen von 3):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Schritt 2.3 (Die nächste unmarkierte Zahl ist die 5):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Schritt 3.3 (alle Vielfachen von 5 sind bereits markiert):
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Weitere Schritte benötigen wir nicht, da die nächste unmarkierte Zahl in der Liste die 7 ist und 7 * 7= 49 und 49 > 20.
Folglich sind alle restlichen Zahlen in unserer Liste Primzahlen:
2 – 3 – 4 – 5 – 6 – 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 – 16 – 17 – 18 – 19 – 20
Um diesen Algorithmus exakt wie in dem Beispiel mit C# umzusetzen, erstellen wir zunächst eine Funktion namens findPrimes, die als Parameter unsere Grenze (max) annimmt und eine Liste der Primzahlen als List<int> zurückgibt:
static List<int> findPrimes(int max)
{
}
Die Funktion ist static, da diese in unserer einfachen Konsolenanwendung aus der Main Funktion heraus aufgerufen wird.
In unserer Funktion benötigen wir zunächst zwei Variablen, genauer eine Liste, in der wir später die gefunden Primzahlen ablegen, und ein Array mit allen Zahlen von 0 bis zur Grenze (max). Das Array ist vom Typ bool, wobei der Wert true für Primzahl und der Wert false für keine Primzahl steht.
List<int> primes = new List<int>();
bool[] numbers = new bool[max];
Bevor wir weiter machen überprüfen wir noch die als Parameter übergebene Grenze (max), denn wenn diese kleiner als zwei ist, brauchen wir gar nicht weiter machen. In dem Fall gibt es keine Primzahlen und wir geben die vorher initialisierte leere Liste primes zurück.
if (max < 2) return primes;
Als nächstes setzen wir alle Werte in numbers auf true. Das heißt alle Zahlen sind primär als Primzahl markiert und wir werden im weiteren Verlauf alle Vielfachen der Primzahlen als keine Primzahl (false) markieren.
for (int i = 0; i <= max; i++)
{
numbers[i] = true;
}
Nun deklarieren wir eine neue Variable und setzen sie auf die erste Primzahl (2). Diese Variable nennen wir p, was für die aktuelle Primzahl bzw. die aktuelle Position steht.
int p = 2;
Anschließend führen wir in einer Schleife die oben beschriebenen Schritte 2 und 3 aus, bis das Quadrat der aktuellen Primzahl größer als die Grenze ist.
while (p * p <= max)
{
for (int i = p + p; i <= max; i += p)
{
numbers[i] = false;
}
int x = p + 1;
while (numbers[x] == false) x++;
p = x;
}
In der Schleife gehen wir mit Hilfe einer For-Schleife alle Vielfachen der Primzahl p durch und markieren sie als false (= keine Primzahl). Wir beginnen dabei erst bei p+p, da p selbst ja noch eine Primzahl ist und nicht als false markiert werden soll.
Im zweiten Teil der While-Schleife (s.o.) gehen wir das Array so lange durch, bis wir zur nächsten als Primzahl markierten Zahl kommen bzw. zur nächsten Zahl, die nicht als Vielfaches markiert ist. Diese ist dem Algorithmus nach dann automatisch wieder eine Primzahl. Der Vorgang wird dann wiederholt bis die Bedingung für die While-Schleife nicht mehr erfüllt ist.
Anschließend müssen wir alle als Primzahl markierten Zahlen im Array finden und unserer am Anfang deklarierten Liste primes hinzufügen:
for (int i = 2; i <= max; i++)
{
if (numbers[i] == true) primes.Add(i);
}
Nicht vergessen diese Liste am Ende noch zurück zu geben:
return primes;
Der komplette Code
Im folgenden sehen wir den kompletten unkommentierten Code, der so kompilierbar und ausführbar ist. Das Programm findet alle Primzahlen bis 1000 und gibt diese in der Konsole aus.
using System;
using System.Collections.Generic;
namespace PrimeFinder
{
class Program
{
static void Main(string[] args)
{
List<int> primes = findPrimes(1000);
foreach (int prime in primes)
{
Console.Write(prime.ToString() + "; ");
}
Console.ReadKey();
}
static List<int> findPrimes(int max)
{
List<int> primes = new List<int>();
bool[] numbers = new bool[max+1];
if (max < 2) return primes;
for (int i = 0; i <= max; i++)
{
numbers[i] = true;
}
int p = 2;
while (p * p <= max)
{
for (int i = p + p; i <= max; i += p)
{
numbers[i] = false;
}
int x = p + 1;
while (numbers[x] == false) x++;
p = x;
}
for (int i = 2; i <= max; i++)
{
if (numbers[i] == true) primes.Add(i);
}
return primes;
}
}
}
Die Ausgabe der Konsole sieht dann so aus:
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; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503; 509; 521; 523; 541; 547; 557; 563; 569; 571; 577; 587; 593; 599; 601; 607; 613; 617; 619; 631; 641; 643; 647; 653; 659; 661; 673; 677; 683; 691; 701; 709; 719; 727; 733; 739; 743; 751; 757; 761; 769; 773; 787; 797; 809; 811; 821; 823; 827; 829; 839; 853; 857; 859; 863; 877; 881; 883; 887; 907; 911; 919; 929; 937; 941; 947; 953; 967; 971; 977; 983; 991; 997;
Nachwort
Dieser Algorithmus ist sehr einfach umzusetzen, erfordert beim Ausführen aber eine gewisse Rechenzeit, da viele Schleifen durchgegangen werden müssen. Der Code lässt sich optimieren, indem zum Beispiel beim initialisieren des Arrays am Anfang bereits alle geraden Zahlen auf false gesetzt werden. Dadurch spart man sich die erste und längste Schleife beim Berechnen der Vielfachen. Sicher gibt es noch den ein oder anderen Trick um die Performance weiter zu verbessern und um die Speicherauslastung zu reduzieren, da rum sollte es aber in diesem Tutorial nicht gehen.