Fő tartalom

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?

Jelentkezz be

Rendezés:

Még nincs hozzászólás.

Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.