Programozás

[tulip]

Originally Posted by Redback

az megkérdezhetem, hogyan keresed a prímeket? mert szerintem a gyökéig osztogatóssal ezt lehetetlen megoldani.még arra gondolok, hogy egy nagyon nagy tömbben mindig kivenni az i. és k*i. elemet, ( k eleme a pozitív egész számoknak ) majd növelni i értékét.

1, Legenerálom a prím számokat a vizsgálandó legnagyobb szám gyökéig.
2, Megadok egy 50.000 elemes boolean tömböt (50.000 fölött nem gyorsult tovább) és darabonként eratoszthenészi szitával fedem le a teljes tartományt. De mindig csak egyetlen tömb van jelen a memóriában, azaz tologatom a lefedő tömböt.

Tehát először megvan az 1-es pont, ezt egyszer végzem el. Ez után, ha valamelyik számról el akarom dönteni, hogy prím-e, pl. a 120121-ről, akkor a program megvizsgálja, hogy le van-e fedve eratoszthenészi szitával. Ha nincs, akkor 120121-től kezdődően 120121+49999-ig elkészíti az eratoszthenészi szitát, figyelembe véve, hogy a tömb 0-49999-ig van sorszámozva és a 0 itt a 120121-et fogja jelölni. Természetesen itt is csak a gyök(120121+49999)-ig folyik a vizsgálat.

Hogy érthetőbb legyen. Ha úgy választunk meg 2 vizsgálandó számot, hogy a különbség köztük nagyobb, mint az 50.000-es tömb, pl. 2 és 120121-ről szeretnénk eldönteni, hogy prímek-e, akkor megkeresi az algoritmus 2-50001-ig az összes prímet és megkeresi 120121-170120 között az összes prímet, tehát egy halom felesleges számolást végez. Ellenben ha pl. megnézzük a 2, 11201, 503, 57,45511, 27 számokra, akkor csak egyetlen, 2-49999-ig tömböt fog kiszámolni.

Tehát ez az algoritmus akkor igazán gyors, ha sorban növekvő elemeket akarunk vizsgálni.