Allgemeines zu Primzahlen


Was sind Primzahlen?

Primzahlen sind natürliche Zahlen (ganze Zahlen >= 0), die nur durch zwei natürliche Zahlen geteilt werden können, ohne, dass es einen Rest gibt. Diese beiden Teiler sind im Allgemeinen immer die Zahl selbst und die Zahl 1. Die beiden Teiler müssen selbstverständlich verschieden sein. Daher ist die Zahl 1 auch keine Primzahl, denn sie hat nur den Teiler 1.
Beispiele für Primzahlen sind die Zahlen 2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 ...
Alternativ verweise ich an dieser Stelle auch auf die Liste der ersten 1.000.000 Primzahlen (Größe: 8,81MB! - Öffnen dauert evtl. etwas).

Wenn man nun die Zahlen genauer betrachtet, fällt auf, dass diese alle ungrade sind (Ausnahme: 2) und alle auf 1, 3, 7, oder 9 enden (Ausnahme: 2 und 5). Diese Eigenschaft kann man natürlich bei der Berechnung mittels eines Computerprogramms nutzen. So macht es zumindest mein Primzahlenberechnungsprogramm und es rechnet dadurch etwa doppelt so schnell wie ohne die Berücksichtigung dieser Eigenschaften.

Gibt es eine Formel für Primzahlen?

Nein, die gibt es leider nicht.
Um Primzahlen mit dem Computer zu berechnen, verwendet man oftmals den Modulo-Operator(%). Dieser liefert den Rest einer Division.
Zum Beispiel 7 % 4 = 3, denn 7 / 4 = 1 Rest: 3, da 1 * 4 + 3 = 7
Wenn x % i = 0 ergibt, es also keinen Rest gibt, ist die Zahl x durch i teilbar.
Um in einem Computerprogramm zu prüfen, ob eine Zahl x eine Primzahl ist, kann man so vorgehen:

  1. i wird auf 1 gesetzt. n (speichert, wie oft x restlos geteilt werden konnte) wird auf 0 gesetzt.
  2. Es wird x % i gerechnet.
  3. Wenn das Ergebnis 0 ist, wird n um 1 erhöht, da x restlos durch i geteilt wurde.
  4. Wenn n = 3 oder sogar größer als 3 ist, wird es abgebrochen, da die Zahl keine Primzahl mehr sein kann.
  5. Wenn i kleiner als x ist, wird i um 1 erhöht und wieder bei Schritt 2 angefangen.
  6. Wenn i nun gleich x ist und auch schon mit diesem Wert von i gerechnet wurde und n = 2 ist, handelt es sich um eine Primzahl.

Und so sieht der Programmcode in Java für ein solches Programm aus:

int n = 0;
boolean isPrimzahl = true;
int x = 31; //eine Zahl zum Pruefen
for (int i = 1; i <= x; i++) {
    if (x % i == 0) {
        n++;
        if (n >= 3){
            isPrimzahl = false;
            break;
        }
    }
}
if (isPrimzahl) {
    System.out.println(x + " ist eine Primzahl.");
}
else {
    System.out.println(x + " ist keine Primzahl.");
}

Dieser Programmcode kann natürlich noch um einiges optimiert werden. Zum Beispiel kann man gerade Zahlen und Zahlen, welche auf 5 enden, direkt aussortieren (natürlich muss man dann auch noch einen Teil bauen, der prüft, ob es sich nicht um die Zahl 2 oder 5 handelt, da diese ja sonst aussortiert würden), um das Programm zu optimieren.


Ein weiteres Verfahren zur Berechnung von Primzahlen ist das Sieb des Eratosthenes.
Hier wird eine Liste aus allen Zahlen erstellt und anschließend werden immer die Vielfachen einer Zahl gestrichen. Dieses Verfahren benötigt jedoch recht viel Speicher für die Liste, weswegen ich es in dieser Form nicht im Primzahlenberechnungsprogramm eingesetzt habe.
So sieht ein Javaprogramm für dieses Verfahren aus:

//Initialisierung des Arrays mit allen Zahlen von 2 bis MAX
zahlen = new int[MAX];
for (int i = 2; i <= MAX; i++) {
    zahlen[i-2] = i;
}

//Anwendung des Siebs
for (int i = 2; i <= Math.sqrt(MAX); i++) {
    for (int j = 0; j < MAX; j++) {
        if (zahlen[j] > i && zahlen[j] % i == 0) {
            zahlen[j] = -1; //Streichen der Zahl
        }
    }
}

//Ausgabe
for (int i = 0; i < MAX; i++) {
    if (zahlen[i] > 0)
        System.out.println(""+zahlen[i]);
}

Dieses Programm kann natürlich auch noch um einiges optimiert werden. Hier könnte man beispielsweise nur die Vielfachen von bereits gefundenen Primzahlen streichen anstatt von jeder Zahl.



Diese Seite wird noch weiter ergänzt...
Bei Fragen, Kritik, Vorschlägen für diese Seite etc. bitte einfach bei mir melden.