If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

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 n1 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= 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 scratchpad 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, ez a lecke teljesíthető programozás nélkül is).

Szeretnél részt venni a beszélgetésben?

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.