Hogyan tudom meghatározni max. O (n^2) -es futási idővel egy sztring összes egyszeres zárójelezését?

Erről az jut eszembe, mikor fősulin vizsgán volt egy relatíve egyszerű feladat, írj pascal programot, ami kiírja 1-től 1000-ig a prímszámokat. Mindenki nekiállt valami algoritmus összehozni ki így, ki úgy. Egy srác a következő programot írta:

writeln('2');

writeln('3');

writeln('5');

writeln('7');

writeln('11');

…

Ott helyben javította a tanár a feladatokat, és mi is láttuk, ki mit írt. Mindenki felröhögött a srác megoldásán. A tanár ennyit mondott: „Mit röhögtök? Az volt a feladat, hogy a program kiírja a prímszámokat. Kiírta? Igen. Akkor a feladat teljesítve. Még gyorsabb is, mint a ti megoldásotok.”

Oké, de értelme volt a dolognak? Persze ha a proci a szűk keresztmetszet, lehet kvázi előre legyártott adatokkal dolgozva ezen segíteni, de cserébe több memóriát foglal, és/vagy nagyobb lesz a program. Jelen esetben annyi a lehetőség, hogy ugyan elvileg egy maximális hosszra lehet ezt csinálni, de 256 karakter hosszú stringnél is más csúnyán nagy táblázat kellene. Nem igazán látom értelmét a dolognak. A részoptimalizálással – hogy mondjuk 16 karakteres stringeket táblázatból vesz, de ott is össze kell kombinálni a részstringeket, amivel nem nagyon nyersz.