a) habe aus Versehen y für x geschrieben
Input(y)
x:=0
wiederhole
x:=x+1
bis x•x ≥ y
wenn 4y < 4•x•y - 4•x +1 dann x:= x-1
[ Kommentar: x-√y > √y - (x-1) <=> 2√y < 2x - 1 <=> 4y < 4•x•x - 4•x +1 ]
Output(x)
---------------------
b)
Input(n)
p ::= 1 [auf Primzahl zu prüfende Zahl]
wiederhole
p:= p + 1
t := 1 [möglicher Teiler von p]
wiederhole
t := t +1
g:=1 [möglicher Gegenteiler von t]
wiederhole
a:=0 [Anzeiger für Teiler]
g := g+1
wenn p = g • t dann a := 1
bis g = n oder a = 1
wenn a = 0 dann output(x)
bis t = n
bis p = n
-----------------------------
Der Algorithmus ist nicht optimiert. Man könnte als Obergrenze der Hauptschleife auch √n nehmen, wegen der Einschränkung der Operatoren "vertreten" durch den in a) berechneten Wert x ≈ √n .Input(n) müsste dann durch den vorgeschalteten Algoritmus von a) ersetzt werden. Aber das wäre nur Maßnahme zur Laufzeitoptimierung.
Logischerweise konnte ich die - wegen der Operatoreneinschränkung sehr ungewöhnlichen -Algoritmen nicht überprüfen. Bau sie also nicht in eine Flugzeugsteuerung ein. :-)
