Ukotveme si zakladni remeslnou zdanost v jazyce C. Doporucuji Vam implementovat ulozky inkrementalne, nejdrive zacit s jednoduchou funkcni verzi a tu pak postupne vylepsovat. Nemate-li radi textove editory, muzete zkusit pouzit gedit nebo kate. Zakladni prepinace programu gcc jsou -Wall Piste vzdy, usetrite si spoustu nervu -O3 Zapne nejvyssi uroven optimalizaci; bez prepinace nejsou programy optimalizovane _vubec_ -std=gnu99 Preklad podle normy C99 plus GNU rozsireni Zajima-li Vas, kolik mate volne pameti a na jakem CPU Vas program bezi, zkuste prikazy free cat /proc/cpuinfo Pro vypisovani cisel pouzijte #include ... printf("%d\n", cislo); pro alokaci pole pak treba bool *p = calloc(n, sizeof(p[0])); (calloc zarucuje zinicializovanou pamet; odkazem na p[0] se vyvarujeme spatne velikosti alokace z prehlednuti; pozor, malloc bere velikost pameti v bajtech (charech), ne poctu polozek pole!) (i) Napiste program, ktery vypise {x : 1 <= x <= 1000, x \in N} (ii) Napiste program, ktery vypise {x : 1 < x <= 1000, x \in PRIMES} (iii) Napiste program, ktery vypise |{x : 1 < x <= 10^9, x \in PRIMES}| Tedy pocet prvocisel mensich nez miliarda. Obecnejsi varianta ulohy (iii) (horni mez zadana jako parametr) je pak i prvni domaci ukol. ---- Hinty a reseni (iii) Primerena implementace by mohla bezet na modernim CPU radove 15s az 30s, zrychlit jde dale peclivou optimalizaci klidne i na tretinu. Mame-li horni mez na prvocisla, ktera nas zajimaji, casto se vyuziva algoritmus Erastothenovo sito. Musime si rozmyslet, ze se pole vejde do pameti; v pripade 10^9 a polozkou bool (bajt) zabere zhruba 1GiB, coz v dnesni dobe nebyva problem. Dalsi okamzity postreh pro zrychleni algoritmu je jednoduchy fakt z teorie cisel - je-li cislo x slozene, alespon jeden jeho delitel je <= sqrt(x). Pri implementaci nas nejcastejsi chyby potkavaji v implementaci cyklu oznacujiciho v situ nasobky prvocisla; bud jsou spatne meze cyklu, nebo inkrement (omylem prejdeme na dvojnasobek akt. cisla misto dalsiho nasobku puvodniho cisla). Algoritmus muzeme dale optimalizovat. Misto bajtu muzeme pracovat s polem bitu. Muzeme mit v situ pouze licha cisla, dokonce si muzeme rozmyslet, ze kazde prvocislo (krom prvnich) muzeme popsat jako 6k+-1 (pro prirozene k). Bitove pole si muzeme predinicializovat urcitym bitovym patternem a nektere operace predpocitat do tabulky. K dalsim triku se vratime i pozdeji behem semestru.