Az eratosztenészi szita

Be fogok mutatni egy ősi eljárást, amivel elő tudjuk állítani a prímszámok listáját egy adott N határig, amit eratosztenészi szitának hívnak. Eratosztenész Kr.e. 276-ban született, úgyhogy ez a módszer több, mint 2200 éves. De nagyon egyszerű és elegáns, bármelyik kisgyerek meg tudja tanulni. Például ki szeretnénk számolni az összes prímszámot 100-ig, de a módszer ugyanúgy működik, ha 10 000-ig vagy egymillióig szeretnéd kiszámolni. A következőképpen kell csinálni. Még egy szám sincs megjelölve, minden szám szürke. Az elejéről indulunk. Ha találunk egy számot, ami nincs megjelölve, akkor tudjuk, hogy az prím. Rálépünk 2-re, és azt mondjuk, hogy 2 prím, mert nincs megjelölve. A következő lépésben kizárjuk a 2 összes többszörösét, mert tudjuk, hogy azok összetettek. Bumm, így haladunk előre, és kiiktatjuk a 2 összes többszörösét, a piros jelenti az összetett számot. Aztán mindent megismétlünk. A 2-ről a 3-ra lépünk. 3 nincs megjelölve, tehát megjelöljük prímként. Most kizárhatjuk a 3 összes többszörösét. Egy nagyon egyszerű optimalizálás: látod, 6 már ki van zárva, elég a kizárást a szám négyzeténél elkezdeni. Tehát 3 · 3 = 9, 9-nél indulunk, majd innen a 3 többszöröseit megjelöljük összetettként. Majd visszamegyünk, és továbblépünk 4-re. A 4 már meg van jelölve, tudjuk, hogy összetett. Továbblépünk 5-re, ez még jelöletlen, az 5 prímszám. 5 · 5 = 25, továbblépünk 25-re, megjelöljük a 25-öt, 30-at, 35-öt, 40-et, 45-öt és így tovább. Ezek az összetett számok. Addig folytatjuk, amíg elérünk 7-hez, tudjuk, hogy prímszám, mert nincs megjelölve.·· 7 · 7 = 49, megjelöljük 49-et és a 7 összes többszörösét összetettként. Továbblépünk 11-ig, 11 prímszám. ... és ... Most látod, 11 · 11 nagyobb, mint 100, úgyhogy itt megállhatunk. Már a 10-nél megállhattunk volna, mert most már minden jelöletlen szám prímszám lesz. Egy lendülettel mindet megjelölhetjük prímszámként. Ez a teljes algoritmus, ennyire egyszerű. Általánosítsuk, hogyan csináltuk mindezt, hogy elkészíthessünk egy programot, ami megcsinálja ezt a szitát, amivel megkereshetjük egy adott n-ig az összes prímszámot. Először elkészítjük a külső ciklust. Vesszük az összes a-t 2-től négyzetgyök n-ig. Itt már kiszállunk 10-nél. 11-nél mutattam az előbb, ahol megállunk, mert megtaláltuk az összes prímszámot. Szóval, 2-től négyzetgyök n-ig az alábbiak szerint haladunk: ha 'a' jelöletlen, akkor tudjuk, hogy 'a' prímszám, ha találunk egy prímet, akkor a-nak az összes többszörösét megjelöljük összetettként. Ennyi az egész. Tehát ha találsz egy prímet jelöld meg a többszöröseit, menj vissza az elejére, növeld meg a-t eggyel. 2-vel kezdjük, továbblépünk 3-ra, majd 4-re, 5-re és így tovább. És amikor készen vagyunk, megvan az összes prímszám. Figyeld meg, hogy ez is egy ciklus. Van egy külső ciklusunk, ahol keresünk egy prímet. Ahol megjelöljük a többszörösöket, az is egy ciklus. Fontos megérteni, hogy itt egymásba ágyazott ciklusokról van szó, a cikluson belül van egy másik ciklus. Itt megmutatjuk a programot működés közben, amit JavaScriptben írtam. Ha elindítom 100-al, itt az összes prímszám 100-ig, Ha 200-at adok neki, itt az összes prímszám 200-ig, és ha 850 a bemenet, itt az összes prímszám 850-ig, A következő leckében megnézheted a programot, amit ehhez írtam.