C programozásban prímszám-e feladatot gyökösként is megtudom csinálni, csak nem teljesen értem. A kérdés tehát az lenne, hogy hogyan végzi el a számításokat a gyökös prímszám ellenőrző?

„3,8729-t felkerekíti 4-re”

Ugyan, miért kerekítené fel? A gyök lehet lebegőpontos szám, attól még összehasonlíthatod egy egésszel. De ha valami miatt egészként akarod tárolni, akkor kétségkívül felkerekíted. És akkor mi van? Ott egye meg a fene.

Úgy tűnik, mintha nem lenne világos a számodra a gyökig való vizsgálat szerepe. A lényeg, hogy a szám gyökénél nagyobb esetben már olyan osztópárok következnek, amelyeket már voltak, és ezeknek a fölösleges vizsgálatát spórolod meg a korlátozással. Persze, előre meg lehetne nézni, hogy kerekítés után nagyobb lett-e a gyök, és akkor elég eggyel kevesebbszer vizsgálni -- csak éppen több vele a macera, mint a haszon, azalatt már inkább végezze el azt az egyetlen szükségtelen lépést.

De ha kerekítene, akkor sem lenne szükségtelen lépés, hiszen 3 < 3,87, és isteni szerencsénkre 3 < 4 detto igaz; még nagyobb szerencsénkre viszont a 4 < 4 már nem igaz.

Ha kerekít, 3-ig számol el, ha nem kerekít, akkor 3-ig számol el. Ezen nem éri meg rugózni.

@#2:

Ja, kezd tisztulni a kép, marad az eleje annak, amit írtam. Sqrt(akármi) akkor sem egész számot ad vissza, ha akármi amúgy egész szám volt. Amíg erőnek erejével bele nem rakod egy int változóba, addig nincs vele probléma, mellesleg akkor viszont szerintem nem fölfelé kerekít, hanem levágja a törtrészt -- de ezt erősítse meg olyan, aki ismeri a C-t.

Viszont gyök(25)-tel szívás lesz így, mivel az 5

igy i<gyök(25) esetén az i=5-öt nem fogja vizsgálni, azaz a 25-öt prímszámnak fogja venni.

@#5:

Hüm, igaz... Hajlamos vagyok túlbonyolítani, bocs.

#6os vagyok. De hogy valami hasznosat is mondjak, sztem így írd a ciklust:

for (int i=2; i*i<=szam; i++)

Ekkor nincs gyökszámítás, ami nem "olcsó", nincs lebegőpontos szám, stb.

Mindenképp <= vizsgálat kell, különben gond lesz az olyan számokkal, mint a 25, aminek egész a négyzetgyöke.

Az említett 15 esetén ugye 2-vel nem osztható, megy tovább, 3-mal osztható, tehát ki is léphetünk: nem prímszám. Ha kerekítve 4-ig megvizsgálná, akkor sem volna semmi, mert a 3 miatt már megállapítottuk, hogy nem prím.

Tehát: 2-től addig kell vizsgálni, amíg nem találsz egy osztót, de legfeljebb a négyzetgyökéig. 15 esetében: 4-gyel nem osztható, de ami 2-vel nem osztható, az 4-gyel sem. 5-tel osztható, az eredmény 3, de ugye 3-mal már tudjuk, hogy osztható, szóval ezt is fölösleges vizsgálni és így tovább.

Rengeteg ciklust lehet így megspórolni.