C++ -ban hogyan lehet meghatározni egy bekért szám legkisebb osztóját?

Prímszám meghatározásához a gyökéig kell eljutni, ezt egy jobb képességű általános iskolás is kitalálta volna, még annak idején ezt a kérdést adták nekünk egy megyei matematika versenyen, a legtöbben kitalálták.

Végigiterálsz az összes prímszámon a kettőtől a szám négyzetgyökéig. De egyesével is lehet, meg el lehet menni egészen a végéig is, kis 8 jegyű prímszámok alatt még nem baj, csak feleslegesen tart sokáig:

for(int i = 2; i < a; i++){

if(a%i==0){

a = i;

}

}

cout<<a;

"Aha, értem, és ha ez egy pozitív szám, ami nem prím, akkor mit kell még csinálni, hogy kiírja a legkisebb osztót, ami nem az 1-es"

Ott van, megcsináltad. Ha azt kérdezed, mit kéne az if-be írni.. a kiíratást. Ennyi. Meg kilépni, hogy ne fusson tovább a ciklus. Ha belép abba az elágazásba, az azt jelenti, hogy talált osztót. Mi az osztó? i. Ezt kell kiírni.

Egyébként igen, a leghatékonyabb, ha a prímszámokon mész végig, de mivelhogy a prímek előállítása lassú, és kevés műveletet kell végezned egy iterációban (egy moduloszámítás, és egy feltételellenőrzés), ezért hacsak nem áll előre rendelkezésre megfelelő nagyságig az összes prímszám, egyszerűbb csak 2-től iterálni. Egy apró optimalizálás mondjuk, ami felezi az iterációk számát, ha 3-tól indítod a ciklust, és kettesével lépsz. Ennek oka, hogy a páros számokra fölösleges ellenőrizni, ha 2-vel nem osztható a szám, akkor 4-el, 6-el, stb. sem lesz az. Persze ehhez először külön le kell ellenőrizned, hogy 2-vel osztható-e, és ha nem, csak akkor indítod el a ciklust.

"prímek előállítása lassú"

Eratoszthenész szitája O(log n) időbonyolultságú, és mivel csak a gyökéig kell elmenni, ezért a tárbonyolultsága is O(log n). Ez nem elég gyors? Konstans időben akarod számítani?

Ide lehet, hogy nem kellene írni, úgyis csak azt pontozzák le, aki leírja a megfejtést...