Primzahl/Programm/Nur Addition/Aufgabe

Man entwerfe ein Computer-Programm (Pseudocode), das zu einer vorgegebenen Zahl ${}n\geq 2$ entscheidet, ob ${}n$ eine Primzahl ist oder nicht.

• Der Computer besitzt beliebig viele Speicher, die natürliche Zahlen enthalten können.
• Er kann einen Speicher leeren.
• Er kann einen Speicherinhalt um ${}1$ erhöhen.
• Er kann die Summe von zwei Speicherinhalten ausrechnen und in einen Speicher schreiben.
• Er kann Speicherinhalte miteinander vergleichen und abhängig davon zu einem bestimmten Befehl wechseln.
• Er kann Speicherinhalte ausdrucken und vorgegebene Texte ausdrucken.
• Es gibt einen Haltebefehl.

Die Anfangskonfiguration sei

$(n,0,0,0,0,0,0,\ldots )$

mit ${}n\geq 2$. Das Programm soll „${}n$ ist eine Primzahl“ oder „${}n$ ist keine Primzahl“ ausdrucken und anschließend anhalten.

Zur Lösung, Alternative Lösung erstellen