Prímteszt szitával

Ismételjünk! Próbálkozásos osztással ellenőrizzük, hogy egy tetszőleges N szám prímszám-e. Itt van N négyzetgyöke, és itt van a 3. 3-nál indulunk, és kettesével megyünk előre, amíg eljutunk négyzetgyök N-ig. Minden lépésnél ellenőrizzük, hogy az a szám osztója-e N-nek. Eddig arra törekedtünk, hogy csökkentsük a szükséges lépések számát úgy, hogy később indulunk, és nagyobbakat lépünk. Itt egy kicsit megállnék: gondolkodjunk el azon, mi lenne az ideális a próbálkozásos osztás algoritmusához? Mi a legtöbb, amit tehetünk, ha nagyon kreatívan lépegetünk? Ne feledd, minden N számhoz tartozik prímtényezős felosztás. Tegyük fel, hogy itt az N négyzetgyöke. Csak a prímszámokra kell rálépnünk. Ez a legjobb, amit tehetünk. Tudjuk, hogy ha csak a prímszámokra lépünk, előbb-utóbb találunk egy osztót. Prímosztót, ha összetett szám. Most az a kérdés, mennyire hatékony ez a módszer? Úgy tűnik, megtaláltuk a tökéletes megoldást: ha írunk egy új algoritmust, ami először meghívja a szitát. Mondjuk az új algoritmus azt számolja, hogy N prím-e. Meghívhatod a szitát, és generálhatsz egy szép, hosszú prímekből álló listát. Ezután jön a próbálkozásos osztásunk, ami ezt a prímszám listát használja. Csak prímszámokra ugrana mindaddig, amíg eléri N négyzetgyökét, akárhol is van. Mi a baj evvel? Megnézhetjük az időigényét vagy a szükséges lépések számát. Ezt itt is így csináltam, előszedtem ezt az algoritmust, és betettem egy lépésszámlálót minden egyes ciklusba – itt van egy Step plusz plusz, ami azt jelenti, lépés plusz 1. A másik ciklusban is van egy lépésszámláló itt. Step plusz plusz. Ezek konstans műveletek, egy vizsgálat és egy jelölés. Tehát van egy lépésszámlálónk minden ciklusban. Itt az összehasonlítás: a bal szélen van a régi próbálkozásos módszerünk. Középen van az algoritmus, ami meghívja a szitát, ami N-ig generálja a prímszámokat. A jobb oldalon az a javasolt megoldás található, ahol a szitát csak gyök N-ig generáljuk, és a próbálkozásos osztást csak ezekkel a prímekkel végezzük el. Lássuk, mi történik egy kis bemenettel. Láthatjuk, hogy a szitához sok lépés kell. Még a jobb oldali módosított verzió is lassabb, mint a próbálkozásos osztás. Ahogy nő a bemenet, a szita lépésszáma még gyorsabban nő. Hagyjuk el a középső eljárást, és csak a próbálkozásos osztást hasonlítsuk a gyök N-ig számoló szita plusz sima próbálkozásos osztáshoz. Itt azt látjuk, hogy a régi próbálkozásos osztás sokkal hatékonyabb. A gyök N-ig számoló szitának plusz a próbálkozásos osztásnak a lépésszámlálója sokkal gyorsabban nő. Úgyhogy ez nem javít a hatékonyságon. A következő leckében láthatod a programot. Van róla egy magyarázó videó. Felmerülhet az is: „Mi lenne, ha előre kiszámítanánk a prímszámokat?" Az első lépés az lenne, hogy építünk a prímekből egy tömböt, és azt eltárolnánk egy lemezen. Az algoritmusunk csak az osztást végezné, csak prímszámokat használna, amit ebből a tervezett listából olvasna. Lehet, hogy a listánk 20 számjegyig tartalmazná a prímszámokat, vagy akár 100 számjegyig. Ez miért nem járható út? A problémát a memóriakorlát jelenti, amikor hosszú számsorokat állítunk össze. Ezt majd később megvizsgáljuk. A példa kedvéért tegyük fel, hogy manuálisan csináljuk. Kiszámítjuk: az 5 prímszám, felírjuk az 5-öt egy papírra, és betesszük egy iratszekrénybe. Aztán vesszük a 7-et, azt is eltesszük a szekrénybe. 9, ja bocs, 11, megy a szekrénybe. Végül lesz egy iratszekrényünk tele prímszámokkal. Ez lesz a prímszám-tömbünk. Milyen nagy iratszekrény kellene ahhoz, ha 20 számjegyig, vagy akár 100 számjegyig szeretnénk tárolni a prímszámokat? Elférne ez a tömb egy lemezen? Ahhoz, hogy megértsük, ez miért lehetetlen, egy kicsit mélyebbre kell ásnunk abban, hogy milyen nagyra nő ez a tömb, és mik a korlátai a mai és akár a jövő számítógép hardvereknek.