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
Osztáspróba
Definiáljuk a feladatot
Egy olyan gépet kell építenünk, amely képes arra, hogy választ adjon egy egyszerű igen/nem kérdésre: ha megadunk egy n egész számot, n prímszám-e, vagy sem?
Gondoljuk végig, mit kell tudnia a gépnek ahhoz, hogy működjön. Egy gép lépések sorozatát hajtja végre utasítások alapján, amit algoritmusnak hívunk. Bemelegítésként vizsgáljuk meg, milyen az agyadban lévő algoritmus. Válaszolj erre a kérdésre: 49 prímszám?
…
Nem? Hogyan jutottál erre a következtetésre? Valószínűleg megkerested a 49 egyik osztóját, ami kisebb vagy egyenlő 49-nél. Ha nem tudod fejből a szorzótáblát, akkor logikusan ezt a sorrendet követted:
- A 2 osztója 49-nek? NEM
- A 3 osztója 49-nek? NEM
- A 4 osztója 49-nek? NEM
- Az 5 osztója 49-nek? NEM
- A 6 osztója 49-nek? NEM
- A 7 osztója 49-nek? IGEN
Megtaláltuk a 49 egyik osztóját (a 7-et), ami bizonyítja, hogy 49 összetett szám.
Fal építése
De mi van akkor, ha azt kérdezem tőled, hogy 2971215073 prímszám-e?
Még mindig próbálkozol? Én az első néhány ezer ellenőrzés után még mindig nem találtam osztót. A kulcskérdés itt az, hogy mikor hagyhatjuk abba a keresést, és jelenthetjük ki, hogy n prímszám? (Hívjuk ezt falnak.) Kiindulópontként tudjuk, hogy n, minus, 1 biztosan fal, (mivel n-nek n osztója). Ha minden számot ellenőrzünk 2971215072-ig, akkor vagy találunk egy osztót (ami azt bizonyítja, hogy n összetett szám), VAGY nem találunk (ami azt bizonyítja, hogy n prímszám).
Építsünk jobb falat
Ez működik, de vajon nem tudnánk eltolni a falat, hogy gyorsabban végezzünk? Ne feledd, számunkra elég megtalálni az első (avagy a legkisebb) osztót. Néha a legkisebb osztó a 2, bár lehet ennél sokkal nagyobb is. Ez elvezet a kulcskérdéshez: milyen nagy lehet a legkisebb osztó?
Ha még emlékszel: minden összetett egész szám két vagy több prímszámból áll össze n, equals P · P …
P akkor a legnagyobb, amikor n-nek pontosan két osztója van, amik egyenlőek. Ezeket a számokat négyzetszámoknak hívják, ilyen például a 9 (9 = 3 · 3) vagy a 49 (49 = 7 · 7). Ezt a legrosszabb esetet úgy modellezzük, hogy a falat n négyzetgyökéhez (sqrt(n)) húzzuk meg.
Győződj meg róla: ha nem találunk négyzetgyök n-nél kisebb osztót, akkor n prímszám. Próbáld meg bebizonyítani! (Egy bizonyítás a lecke alján is található.)
Próbálgatáson alapuló algoritmus
Ezzel megvagyunk, úgyhogy akkor folytathatjuk is. Először fogalmazzuk meg szóban a próbálgatáson alapuló algoritmust:
- Olvass be egy n egész számot;
- Minden x egész számra a {2 ... sqrt(n)} intervallumban ellenőrizd, hogy x osztója-e n-nek;
- Ha találtál egy osztót, akkor n összetett szám, OR ELSE n prímszám.
Ha van gyakorlatod a programozásban, nyisd meg a CSscratchpad linket, és próbáld megírni ezt az eljárást. Ha nincs, akkor továbbmehetsz a következő lépésre, ahol megadtam ennek egy működő változatát, amiből kiindulhatsz. (Csak hogy tudd, meg lehet csinálni ezt a leckét programozás nélkül is).
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.