Drzewo faktoryzacji pierwszej

Rozkład na czynniki pierwsze rozkłada liczbę całkowitą na liczby pierwsze, które mnożą się razem, tworząc ją — taki rozkład, jaki ma każda liczba złożona, i dokładnie jeden. To narzędzie bierze dowolną liczbę całkowitą większą niż 2 i rozkłada ją na czynniki rzeczywiste, a następnie rysuje wynik w postaci drzewa czynników rozgałęziających, którego nauczano w szkole: zacznij od liczby, oddziel jej najmniejszy czynnik pierwszy i dziel pozostałą część, aż pozostaną tylko liczby pierwsze.

Zasada podziału polega na próbnym dzieleniu przez najmniejszą możliwą liczbę pierwszą na każdym kroku: najpierw spróbuj 2, a następnie liczb nieparzystych 3, 5, 7, 9... aż do pierwiastka kwadratowego bieżącej wartości. Dla 360, które jest wyświetlane jako 360 = 2 × 180, następnie 180 = 2 × 90, następnie 90 = 2 × 45, następnie 45 = 5 × 9, następnie 9 = 3 × 3 — pięć podziałów zakończonych sześcioma głównymi liśćmi (2, 2, 2, 3, 3, 5). Policzenie tych liści daje zwartą postać wykładniczą pokazaną na diagramie: 360 = 2³ × 3² × 5.

Wszystko to działa z dokładną arytmetyką BigInt, więc nigdy nie ma zaokrąglania zmiennoprzecinkowego w dół. Próbne dzielenie do pierwiastka kwadratowego jest szybkie w przypadku codziennych liczb, ale staje się wolniejsze, im większy jest najmniejszy współczynnik pierwszy danych wejściowych, więc narzędzie ogranicza wprowadzane dane do 1 000 000 000 000 (10^12) i wyświetla szczery komunikat poza tym, zamiast blokować kartę — przeglądarka nie ma obowiązku wstrzymywać się na gigantycznej liczbie półpierwszej tylko po to, aby udowodnić swoją rację.

Wizualne drzewo czynników jest standardowym sposobem nauczania faktoryzacji liczb pierwszych w szkole i pozostaje przydatne także poza zajęciami w klasie: redukowanie ułamków, znajdowanie największego wspólnego dzielnika lub najmniejszej wspólnej wielokrotności przez porównanie potęg pierwszych, upraszczanie pierwiastków kwadratowych i sprawdzanie, czy liczba jest pierwsza, wszystko sprowadza się do tego samego rozkładu. Wszystko działa lokalnie w Twojej przeglądarce — bez rejestracji, bez konieczności przełączania serwera w obie strony.