MATHEMATISCHES INSTITUT DER UNIVERSITÄT MÜNCHEN Dr. W. Spann, G. Kleen WS 2022/2023

Programmieren II für Studierende der Mathematik

Aufgabe 5

Sei N ∈ ℕ, N ≥ 2. Kennt man die Primzahlen < N, so lässt sich damit die Primfaktorzerlegung einer Zahl n ∈ ℕ mit n < N^{2} durch fortgesetztes Abdividieren der Primteiler bestimmen.

Erstellen Sie dazu eine Klasse Primzahlen, die intern auf einer statischen Komponente vom Datentyp vector<bool> der Länge N für jede Zahl k ∈ ℕ mit k < N speichert, ob sie Primzahl ist oder nicht. Verwenden Sie dazu das Sieb des Eratosthenes, in dem Sie ausgehend von k = 2 alle Vielfachen i·k streichen, sofern i ≥ 2 und i·k < N. Die nächste nicht gestrichene Zahl ist die auf 2 folgende Primzahl. Führen Sie diese Verfahren fort, solange k^{2} < N. Fügen Sie zu dieser Klasse eine statische boolesche Funktion ist primzahl hinzu, die angibt, ob n mit 0 ≤ n < N Primzahl ist oder nicht.

Verwenden Sie folgende Klassen zum Speichern der Primfaktorzerlegung:

class Primfaktor {
  public:
    int p,k;    // zur Darstellung von p^k
};
class Primfaktorzerlegung {
  private:
    list<Primfaktor> lst;  // strikt aufsteigend nach Primzahlen geordnet
};

(a) Erstellen Sie einen Konstruktor, der für Argumente n ≤ N^{2} jeweils die Primfaktorzerlegung n = p_{1}^{k_{1}} ⋯ p_{l}^{k_{l}} berechnet und speichert. Nur Primfaktoren mit k ≥ 1 sollen in der Liste gespeichert werden. Für n = 1 oder kein angegebenes Argument soll die Liste l leer sein. Verwenden Sie bei dieser Berechnung die Funktion ist primzahl aus der Klasse

     Primzahlen.

(b) Überladen Sie den Ausgabeoperator so, dass die Primfaktorzerlegung in der Gestalt p_{1}^k_{1}*… ∗p_{l}^k_{l} ausgegeben wird. (Im Fall einer leeren Liste soll 1 ausgegeben werden.)

(c) Fügen Sie eine Typumwandlungsoperator hinzu, der den ganzzahligen Wert der gespeicherten Primfaktorzerlegung als ganze Zahl vom Typ unsigned long liefert.

(d) Erstellen Sie eine weitere Funktion ist primzahl mit einem Argument vom Typ

     Primzahlzerlegung.

Erstellen Sie ein Hauptprogramm, dass für die Zahlen 2^{j} − 1 (j = 1, …, 64) mit 2^{j} − 1 ≤ N^{2} − 1 jeweils die Primfaktorzerlegung und, sofern es sich um eine Primzahl handelt, zusätzlich den Text Mersenne-Primzahl ausgibt. Überprüfen Sie auch, ob der mit dem Typumwandlungsoperator berechnete Wert mit der zu faktorisierenden Zahl jeweils übereinstimmt und geben Sie eine entsprechende Warnung aus, falls das nicht zutrifft.

Verwenden Sie im Hauptprogramm den Datentyp unsigned long und vereinbaren Sie N ≤ 2^{32} am besten als hexadezimale Konstante.

Bearbeitungszeitraum: bis Donnerstag, 7.12.2022, 16^{00}