Primzahlen
Team
Johanna Riedel, Felix Elser,Arianit Miftari
Definition
Hat eine natürliche Zahl p genau zwei Teiler so wird p Primzahl genannt. Wir bezeichnen [math]\mathbb P[/math] als die Menge aller Primzahlen.
Primzahlsatz
Hier wird die Primzählfunktion zund der Primzahlsatz vorgestellt
Anwendungen
Primzahlen in der Natur
Es existieren Zikadenarten, die sich in einem festen Abstand von Jahren massenhaft über der Erde vermehren und danach wieder unter die Erde zurückkehren. In dieser Zeit sind sie weniger gut vor ihren Fressfeinden geschützt. Die Zikaden haben also einen Vorteil, wenn sie in Jahren über der Erde sind, in denen weniger Fressfeinde auftreten. Einige Zikadenarten nutzen genau diesen Vorteil: Sie vermehren sich im Abstand von 13 oder 17 Jahren über der Erde.
Was passiert also mit ihren Fressfeinden? Für solche, die ohnehin in jedem Jahr auftreten, ändert sich nichts. Allerdings gibt es auch solche, die selbst nur in gewissen Jahren auftreten. Beispielsweise existiert eine zikadenjagende Wespe, die alle zwei bis drei Jahre auftritt. Nehmen wir also eine Art an, die alle 2 Jahre auftritt. Würden sich die Zikaden alle 12 Jahre vermehren, so würde in jedem dieser Jahre auch die Wespenart auftreten und die Zikaden hätten es mit deutlich mehr Fressfeinden zu tun. Nun ist der Zyklus der Zikaden aber 13 Jahre lang. Sie müssen also nur alle 26 Jahre mit jener Wespenart fertig werden. Somit haben sie einen deutlichen Vorteil darin, sich zu vermehren.
Primzahltests
Sieb des Eratosthenes
Das Sieb des Eratosthenes ist eines der ältesten Verfahren zur Bestimmung aller Primzahlen, bis hin zu einer frei wählbaren oberen Grenze. Das Verfahren ist nach dem griechischen Mathematiker Eratosthenes von Kyrene (ca. 276 v.Chr. bis ca. 194 v.Chr) benannt. Konzeptionell arbeitet das Verfahren auf Liste von Zahlen, beginnend mit der 2 bis hin zu der oberen Grenze N. Anschließend werden nacheinander alle Zahlen in dieser Liste betrachtet. Ist die betrachtete Zahl nicht markiert, so ist sie eine Primzahl und alle ihre Vielfachen können gestrichen werden. Ist die Zahl bereits markiert, kann man zur nächsten weitergehen. So werden nacheinander alle Primzahlen aus der Liste "herausgesiebt".
Ablauf des Algorithmus
- Wähle eine obere Grenze N, bis zu der alle Primzahlen bestimmt werden sollen.
- Schreibe alle natürlichen Zahlen von 2 bis N auf (um das Ganze anschaulicher zu machen ordnet man die Zahlen meist in einem rechteckigen Schema an, wobei hier die Vielfachen von 10 am Ender einer Reihe stehen). Im Folgenden werden alle Zahlen die keine Primzahlen sind gestrichen.
- Begonnen wird mit der 2. Die 2 selbst ist eine Primzahl, es können aber alle Vielfachen von 2 gestrichen werden, da sie selbst keine Primzahlen sind.
- Die nächste nicht gestrichene Zahl ist die Primzahl 3. Wieder können alle Vielfachen von 3 gestrichen werden. Begonnen werden kann hier mit der Quadratzahl von 3 (9) (warum?)
- Die 4 wurde bereits im 2. Schritt gestrichen und die nächste Zahl kann betrachtet werden.
- Dieses Vorgehen wird mit allen folgenden Zahlen wiederholt. Ist eine Zahl noch nicht gestrichen worden, wenn man sie betrachtet, so ist sie eine Primzahl und ihre Vielfachen können gestrichen werden. Andernfalls kann die nächste Zahl betrachtet werden.
- Der Vorgang wird wiederholt, bis man bei der oberen Grenze N angelangt ist.
Der Algorithmus selbst ist recht Intuitiv und leicht nach zu vollziehen. Auch erklärt sich durch den Algorithmus, wie der Name "_Sieb_ des Eratosthenes" zu stande kommt.
Bemerkung: Spielt man den Algorithmus durch, kann man schnell erkennen, dass beim Streichen von Kandidaten, viele Zahlen mehrfach gestrichen werden. (TODO: Beispiel) Dabei handelt es sich letztlich um überflüssige Operationen.
#include <iostream>
int main(int argc, const char** argv) {
const unsigned int N = 100;
bool Liste[N] = { false };
// iteriere über alle Zahlen in der Liste
for (int i = 2; i <= N; i++) {
// falls Index noch nicht gestrichen sind
if (Liste[i] == false) {
// streiche alle Vielfachen beginnend mit dem Quadrat der gegenwärtig betrachteten Zahl an der Stelle i
for (int j = i*i; j < N; j += i) {
Liste[j] = true;
}
}
}
// gebe alle Primzahlen aus
for (int i = 2; i <= N; i++){
if (Liste[i] == false){
std::cout << i << std::endl;
}
}
return 0;
}