Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
6. lecke: Prímteszt- Bevezetés
- Feladat: prímszám ellenőrzés
- Osztáspróba
- Mi a számítógép memória?
- Az algoritmus hatékonysága
- 3. szint: feladat
- Az eratosztenészi szita
- 4. szint: eratosztenészi szita
- Prímteszt szitával
- 5. szint: osztáspróba szitával
- A prímszámtétel
- A prímszámok sűrűségének logaritmikus spirálja
- A prímszámok távolsága
- Idő kontra tárhely
- Összefoglaló (hogyan tovább?)
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Prímteszt szitával
Megkísérelünk egy optimalizált próbálkozáson alapuló prímtesztet készíteni az eratosztenészi szita segítségével. Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
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.