Primzahl berechnen, die auf einer gegebenen Zahl folgt.

[coder111]

Hallo,
ich verstehe den Code bis Zeile 33, dannach verliere ich den Überblick. Wärt ihr so nett und würdet mir den restlichen Code erklären?

- Ich verstehe z.B. nicht, warum man die 2 Variablen rest und teiler benötigt.
- Und wie kommt man auf den Wert von der Variablen limit (warum Wurzel ziehen und die beiden casts und dann noch +1 rechnen)?

Spoiler: Code

/* cppbuch/k1/primzahl.cpp
   Beispiel zum Buch von U. Breymann: Der C++ Programmierer; 4. Aufl., korr. Nachdruck 2016
   Diese Software ist freie Software. Website: http://www.cppbuch.de/
*/
// Programm zum Berechnen einer Primzahl, die auf eine gegebene Zahl
// folgt
#include <iostream>
#include <cmath>
using namespace std;
int main() {
  cout << "Berechnung der ersten Primzahl, die >="
          " der eingegebenen Zahl ist\n";
  // Hinweis: Mehrere, durch {\tt \dq} getrennte Texte ergeben
  //  {\em eine} lange Zeile in der Ausgabe.
  long z;
  // {\tt do while}-Schleife zur Eingabe und Plausibilitätskontrolle
  do {
    // Abfrage, solange {\tt z} $\le$ 3 ist
    cout << "Zahl > 3 eingeben :";
    cin >> z;
  } while (z <= 3);
  // Falls {\tt z} gerade ist, wird die nächste
  // ungerade Zahl als Startwert genommen.
  if (z % 2 == 0) {
    ++z;
  }
  bool gefunden{false};
  do {
    /* limit = Grenze, bis zu der gerechnet werden muss.
       sqrt() arbeitet mit  double, daher wird der Typ explizit
       umgewandelt.
    */
    long limit{1 + static_cast<long>(sqrt(static_cast<double>(z)))};
    long rest;
    long teiler{1};
    do { // Kandidat {\tt z} durch alle ungeraden Teiler dividieren
      teiler += 2;
      rest = z % teiler;
    } while (rest > 0 && teiler < limit);
    if (rest > 0 && teiler >= limit) {
      gefunden = true;
    } else { // sonst nächste ungerade Zahl untersuchen:
      z += 2;
    }
  } while (!gefunden);
  cout << "Die nächste Primzahl ist " << z << '\n';
}

Besondere Schwierigkeiten hab ich bei diesem Teilcode

Spoiler: Code 2

do { // Kandidat {\tt z} durch alle ungeraden Teiler dividieren
      teiler += 2;
      rest = z % teiler;
    } while (rest > 0 && teiler < limit);
    if (rest > 0 && teiler >= limit) {
      gefunden = true;
    } else { // sonst nächste ungerade Zahl untersuchen:
      z += 2;
    }

 

[sheel]

Hi

also, die Idee dahinter ist, für eine gegebene Zahl einfach alle möglichen teilenden Zahlen durchzuprobieren, ob die Division wohl nie ohne Rest möglich ist. (Wenn es einmal ohne Rest möglich ist ist es natürlich keine Primzahl, weil dann hat man einen wirklichen Teiler gefunden.). Und wenns mit der Zahl nicht geklappt hat, eben die nächsthöhere versuchen (bei der Suche nach der erstbesten Primzahl größer als z).

Welche Teiler man probiert, um die aktuelle Zahl (ich nenn sie x) auf Primheit zu prüfen sind maximal alle Zahlen zwischen 1 und x (natürlich: 0 macht hier nicht viel Sinn, negative Zahlen auch nicht, x selber auch nicht, und Zahlen größer als x werden nie restlos teilen: Der Rest wird immer genau x sein).

Eine Verbesserung ist dabei, dass man gar nicht erst alle x mit x>z durchgeht (bei der Suche nach der erstbesten größeren Primzahl), sondern nur die ungeraden. Damit braucht man dann auch gar nicht erst prüfen ob x von 2 restlos geteilt wird (dann wäre es ja gerade, und die hat man schon ausgelassen), oder auch von irgendeiner anderen geraden Zahl (Wurde zB.10 restlos Teilen, würden es 2 und 5 auch, und da ist 2 dabei => braucht man nicht).

Zweite Verbesserung (zumindest mathematisch) ist, dass man mi der Wurzel w (w*w=x natürlich) keine Zahlen größer als w aufs Teilersein probieren muss (w selber schon noch). Weil: Wenn es für x einen Teiler t gibt mit t>w, was ist dann x/t ? Da t ja wie gesagt ein Teiler ist und damit restlos dividiert, ist x/t keine Kommazahl und damit auch ein Teiler. Und enn t schon größer als die Wurzel ist, kann x/t nur kleiner sein. Kurz, für jeden Teiler größer als die Wurzel gibts auch einen kleiner als die Wurzel, und es reicht ja dass man einen findet (um zu sagen "keine Primzahl"). Deswegen bei der Wurzel schon aufhören.
Das +1 hat einen programmiermäßigen Grund: Man darf nicht vergessen, dass man hier fast überall mit char/short/int/long arbeitet, die keine Kommastellen haben. Erstens ist limit eine long-Variable, für die Wurzel als 9 würde 3 drinstehen, für die Wurzel aus 10,11,12,13,14,15 auch 3, kein Unterschied. Zweitens hat man später eine Schleife, dass man alle ungeraden Teiler auf Rest prüft, die "kleiner als" die Variable limit sind. Folge daraus: Wenn x zB. 15 ist, math. Wurzel ist 3.8729, Variable limit = 3, würde 15 ohne dem "+1" als Primzahl erkannt. 15/1 wird nicht probiert, es geht erst nach 1 los; 15/2 wird nicht probiert weil 2 gerade ist, und 15/3 wird nicht mehr probiert weil 3 nicht kleiner als das Limit ist. Deswegen hätte man in Limit lieber 4 als 3...

So, genug Theorie...

bool gefunden{false};
  do {
    /* limit = Grenze, bis zu der gerechnet werden muss.
       sqrt() arbeitet mit  double, daher wird der Typ explizit
       umgewandelt.
    */
    long limit{1 + static_cast<long>(sqrt(static_cast<double>(z)))};
    long rest;
    long teiler{1};
    do { // Kandidat {\tt z} durch alle ungeraden Teiler dividieren
      teiler += 2;
      rest = z % teiler;
    } while (rest > 0 && teiler < limit);
    if (rest > 0 && teiler >= limit) {
      gefunden = true;
    } else { // sonst nächste ungerade Zahl untersuchen:
      z += 2;
    }
  } while (!gefunden);
  cout << "Die nächste Primzahl ist " << z << '\n';

Die erste Primzahl größer als z ist gesucht. Bisher hab ich sie x genannt, der Code verwendet aber die z-Variable, die immer wieter erhöht wird (den Anfangswert von z braucht man später nicht mehr, kann man also machen).

Als erstes wird für das aktuelle x bzw. z eben das Limit ausgerechnet, ungerade Zahlen zwischen 1 und Limit werden dann probedividiert (natürlich muss z für diese Optimierung auch ungerade sein, wie beschrieben, aber das wird schon in Codezeile 24 und 25 sichergestellt).

Die nächsten 6 Zeilen sind das Probedividieren: teiler=1 (vorerst mal), eine Hilfsvariable rest dazu, und dann immer teiler um 2 erhöhen (ungerade reicht) und den Divisionsrest in Rest speichern solange (rest > 0 && teiler < limit). Wenn man gerade einen Teiler hat, der restlos teilt (und das aktuelle z damit keine Primzahl ist), ist rest 0 und die Schleife bricht ab. Oder, falls man limit erreicht bricht die Schleife auch ab.

Jetzt, nach der Schleife, ist hauptsächlich die Frage, aus welchem der zwei Gründe abgebrochen wurde. Falls es der Limitgrund war ist z prim (alle mögliche Teiler durchprobiert und keiner hatte Rest 0), und beim Rest0 - Grund eben nicht prim. Falls es der Restgrund war ist die Variable rest nach wie vor 0, auch nach der gerade abgebrochenen Schleife. Rest muss beim if danach also größer 0 sein, damit z als Primzahl durchgeht, weil das heißt es war der andere Abbruchsgrund. Der zweite Teil der if-Bedingung ist zwar nicht mehr nötig, passt aber auch dazu: Es war der Limitgrund, und die Schleife ist genau deswegen abgebrochen weil teiler<limit nicht mehr gestimmt hat. Dann muss jetzt wohl teiler>=limit stimmen.

Jetzt man man erkannt, ob z eine Primzahl ist. Falls nicht, zwei dazuzählen und eben das Ganze mit dem nächsten ungeraden z wieder versuchen. Sonst gefunden auf true setzen und damit die größe while(!gefunden) - Schleife zum Ende bringen.