Kalkulator rozkładu na czynniki pierwsze

Rozkład liczby na czynniki pierwsze

Każdą liczbę całkowitą większą od 1 można zapisać jako iloczyn liczb pierwszych dokładnie na jeden sposób, z dokładnością do kolejności czynników. Jest to podstawowe twierdzenie arytmetyki, a rozkład liczby na czynniki pierwsze to właśnie ten jednoznaczny iloczyn. Na przykład 360 = 2³ × 3² × 5. Ten kalkulator znajduje rozkład dowolnej liczby naturalnej do 9,007,199,254,740,991, czyli 2^53 − 1, największej liczby całkowitej, jaką przeglądarka potrafi przedstawić dokładnie. Wyniki są wyświetlane w postaci potęgowej, w postaci w pełni rozwiniętej oraz jako drzewo czynników.

Dzielniki, ich liczba i suma

Gdy znasz rozkład na czynniki pierwsze, wiele innych własności wynika z niego bezpośrednio. Jeśli liczba jest równa p₁^a₁ × p₂^a₂ × …, to liczba jej dodatnich dzielników wynosi (a₁ + 1)(a₂ + 1)…, ponieważ każdy dzielnik wybiera dla każdej liczby pierwszej wykładnik od 0 do pełnej potęgi. Suma dzielników jest iloczynem wyrażeń (1 + p + p² + … + p^a) po wszystkich czynnikach pierwszych. Dla 360 daje to 4 × 3 × 2 = 24 dzielniki o sumie 1170. Narzędzie wypisuje wszystkie dzielniki w kolejności rosnącej, co pomaga w zadaniach takich jak szukanie wspólnych dzielników, skracanie ułamków czy sprawdzanie, czy liczba jest doskonała, czyli czy jej dzielniki inne niż ona sama sumują się do tej liczby.

Jak działa rozkładanie

Małe czynniki pierwsze są usuwane metodą dzielenia próbnego z użyciem koła, które pomija wielokrotności 2 i 3. To, co pozostaje, ma wyłącznie duże czynniki pierwsze, więc kalkulator sprawdza tę resztę deterministycznym testem Miller-Rabin, a jeśli jest ona liczbą złożoną, dzieli ją algorytmem Pollard's rho z użyciem dokładnej arytmetyki BigInt, po czym rozkłada części rekurencyjnie. Dzięki temu nawet iloczyny dwóch liczb pierwszych rzędu dziesiątek milionów są rozkładane szybko, podczas gdy samo dzielenie próbne byłoby powolne. Drzewo czynników pokazuje jeden ze sposobów dojścia do liczb pierwszych przez oddzielanie w każdym kroku najmniejszej liczby pierwszej.

Tryb wsadowy pozwala wkleić całą listę liczb i otrzymać tabelę z rozkładem każdej z nich oraz liczbą dzielników, a nieprawidłowe wpisy są oznaczane osobno, zamiast przerywać całe przetwarzanie. Wszystko jest obliczane w Twojej przeglądarce, więc wpisywane liczby nigdy nie są nigdzie przesyłane.