Die Herausforderung des Primzahltests

Wir beginnen mit einer sehr einfachen Frage. Eigentlich keine Frage, sondern eher eine Herausforderung. Wir müssen eine Maschine bauen, die eine Eingabe entgegennimmt. Diese Eingabe ist eine ganze Zahl X. Und alles, was diese Maschine tun muss, ist, entweder wahr oder falsch auszugeben. Das ist der erste Schritt. Jetzt werden wir uns einem Werkzeug der Informatik bedienen, um diese Maschine tatsächlich gemeinsam zu bauen. Eine der Fragen, die wir uns stellen werden, sind zwei Dinge, zwei Aspekte an dieser Maschine. Wie viel Zeit - das soll eine Uhr sein. Wie viel Zeit braucht sie, um die Lösung auszugeben? Und wie viel Platz benötigt sie? Mit Platz spreche ich im Falle dieser mechanischen Rechenmaschine von physischen Raum. Wie viele Raum brauchen wir, um unsere Maschine unterzubringen? Oder wenn wir einen Computer benutzen, wie viel Speicherplatz braucht dieser? Wir werden auf diese beiden Ideen zurückkommen.