Stablo proste faktorizacije

Rastavljanje na proste faktore rastavlja cijeli broj na proste brojeve koji se međusobno množe kako bi ga dobili — jedno rastavljanje koje ima svaki složeni broj, i to točno jedan. Ovaj alat uzima bilo koji cijeli broj od 2 ili više i rastavlja ga na stvarne faktore, a zatim crta rezultat kao stablo faktora grananja koje se uči u školi: počnite s brojem, odvojite njegov najmanji prosti faktor i nastavite dijeliti preostali dio dok ne ostanu samo prosti brojevi.

Pravilo dijeljenja je probno dijeljenje s najmanjim mogućim prostim brojem u svakom koraku: prvo pokušajte s 2, zatim s neparnim brojevima 3, 5, 7, 9... do kvadratnog korijena trenutne vrijednosti. Za 360 to izgleda kao 360 = 2 × 180, zatim 180 = 2 × 90, zatim 90 = 2 × 45, zatim 45 = 5 × 9, zatim 9 = 3 × 3 — pet podjela koje završavaju sa šest primarnih listova (2, 2, 2, 3, 3, 5). Zbrajanje tih listova daje oblik kompaktnog eksponenta prikazan ispod dijagrama: 360 = 2³ × 3² × 5.

Sve ovo radi s točnom BigInt aritmetikom, tako da nikada nema zaokruživanja s pomičnim zarezom na putu prema dolje. Probno dijeljenje do kvadratnog korijena brzo je za svakodnevne brojeve, ali postaje sporije što je veći najmanji prosti faktor unosa, tako da alat ograničava unos na 1.000.000.000.000 (10^12) i javlja poštenu poruku iznad toga umjesto da zamrzne karticu — preglednik nema posla da visi na ogromnom poluprostom broju samo da bi dokazao svoju točku.

Vizualno stablo faktora standardni je način na koji se rastavljanje prostih faktora podučava u školi i ostaje korisno i izvan učionice: smanjivanje razlomaka, pronalaženje najvećeg zajedničkog faktora ili najmanjeg zajedničkog višekratnika usporedbom prostih potencija, pojednostavljivanjem kvadratnog korijena i provjeravanjem na licu mjesta je li broj prost, svi se vraćaju na istu dekompoziciju. Sve radi lokalno u vašem pregledniku — nema prijave, nema vraćanja poslužitelja.