Miért ez a leggyorsabb módja a prím vizsgálatnak?
Sziasztok!
A leggyorsabb módja (ahogy én olvastam) a prímszámnak vizsgálatnak az, hogyha a ciklust 3-tól indítjuk és egészen a bekért ("vizsgált", melyet nevezzünk most n-nek) szám négyzetgyökéig fut. A kérdésem az, hogy miért?
Tehát:
int root = (int)Math.Sqrt((double)n);
for (int i = 3; i <= root; i += 2)
{
if (n % i == 0) return false;
}
A válaszokat előre is köszönöm! :)
válasza: válasza:
válasza:Mert egy szám gyökénél nagyobb számot egy annál kisebbel kell szorozni, hogy kiadja a számot, tehát nem fogunk találni a gyökénél nagyobb olyan számpárt, amik szorzata a szám lenne.
Mondjuk a 16-ot vizsgáljuk. A lehetséges szorzatok (párok):
1*16
2*8
4*4
8*2
16*1
Vagyis ha 4-ig (gyök 16-ig) eljutottunk, akkor már csak ugyanazok a számok jönnek fel, csak más sorrendben.
válasza:Természetesen nem ez a leggyorsabb módja a prím vizsgálatnak.
Ez csak egy nagyon nagyon egyszerű, kezdők számára is érthető algoritmus, amiben van minimális optimalizáció.
válasza: válasza: válasza:#6: Nem, mert nincs return true;
lehet ez lenne az utolsósorban:
return i == 2 || (i > 1 && (i % 2 == 1));
válasza:Hát az i 3-tól indul és kettesével növekszik, szóval az or második fele igaz, nem?
Illetve mivel tényleg 3-tól indul, az i nem is lehet 2.
Tehát ez egy return true.
Másrészt az i lokális a for-ra nézve, tehát nem is fordul, amit írtál, vagy ha fordul, akkor szemantikai hiba.
válasza:Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!