Tämä viikon tehtävien aiheena on lukuteoria. KKKK:n luvuista 10, 34 ja 35 ovat hyödyllisiä tehtävissä.

Vinkit

Neliösumma

[hint]Mieti ensin, miten kyselet nopeasti, miten luku esitetään kahden neliön summana, mikäli mahdollista.[/hint]

Sovinto

[hint]Soveltamalla Eratostheneen seulan ideaa voit ratkaista ongelman O(m \log m)-algoritmilla, missä m = \max\{p_1, p_2, \ldots, p_n\}.[/hint]

Sulkulauseke

[hint]Yritä soveltaa Wikipedian Catalanin lukujen artikkelin toisen todistuksen ideaa (linkki).[/hint]