Algtegurite tegurpuu

Algteguriteks lahutamine esitab täisarvu algarvude korrutisena, millest see koosneb — iga kordarvu jaoks leidub täpselt üks selline lahutus. See tööriist võtab suvalise täisarvu (alates 2-st), faktoriseerib selle tegelikult ja joonistab tulemuse hargneva tegurpuuna, nagu koolis õpetatakse: alusta arvust, eralda selle väikseim algtegur ja jätka jäägi jagamist, kuni alles on ainult algarvud.

Jagamise reegliks on proovijagamine väikseima võimaliku algarvuga igal sammul: kõigepealt proovi 2, siis paarituid arve 3, 5, 7, 9... kuni hetkeväärtuse ruutjuureni. 360 puhul kulgeb see nii: 360 = 2 × 180, seejärel 180 = 2 × 90, seejärel 90 = 2 × 45, siis 45 = 5 × 9 ja lõpuks 9 = 3 × 3 — viis sammu, mille tulemusel on kuus algarvulist lehte (2, 2, 2, 3, 3, 5). Nende lehtede loendamine annab diagrammi all kuvatava kompaktse astendatud kuju: 360 = 2³ × 3² × 5.

Kõik see toimub täpse BigInt aritmeetikaga, nii ei teki kunagi ujukoma ümardusvigu. Proovijagamine kuni ruutjuureni on igapäevaste arvude korral kiire, kuid muutub aeglasemaks, mida suurem on sisendi väikseim algtegur. Seetõttu piirab tööriist sisendi 1 000 000 000 000-ga (10^12) ja kuvab sellest suurema arvu korral ausa teate, selle asemel et brauseri vahelehte külmutada — veebilehitsejal pole mõistlik tohutu poolalgarvu kallal rippuda.

Visuaalne tegurpuu on tavapärane viis, kuidas koolis algteguriteks lahutamist õpetatakse, ja sellest on kasu ka hiljem: murdude taandamine, suurima ühisteguri või väikseima ühiskordse leidmine algarvu astmete võrdlemise teel, ruutjuurte lihtsustamine ja kontrollimine, kas arv on algarv, taanduvad kõik samale lahutusele. Kõik töötab kohalikult sinu veebilehitsejas — ei registreerumist, ei serveripäringuid.