Matematyka
Rozkład liczby na czynniki pierwsze krok po kroku
Wpisz liczbę całkowitą: otrzymasz jej rozkład na czynniki pierwsze z potęgami, rozkład w słupku jak w zeszycie, listę dzielników i odpowiedź, czy liczba jest pierwsza.
Jak rozłożyć liczbę na czynniki pierwsze
Każdą liczbę całkowitą większą od 1 można zapisać dokładnie w jeden sposób jako iloczyn liczb pierwszych: to podstawowe twierdzenie arytmetyki. Aby je znaleźć, dzieli się przez najmniejszą możliwą liczbę pierwszą, 2, dopóki się da, potem przez 3, przez 5 i tak dalej, zapisując ilorazy w słupku. Dla 360: 360 : 2 = 180, : 2 = 90, : 2 = 45, : 3 = 15, : 3 = 5, : 5 = 1, więc 360 = 2³ · 3² · 5.
Z rozkładu wynika niemal wszystko inne. Liczba dzielników to iloczyn wykładników powiększonych o jeden: dla 360 to 4 · 3 · 2 = 24. NWD i NWW dwóch liczb otrzymuje się, porównując ich rozkłady, a liczba jest kwadratem, gdy wszystkie wykładniki są parzyste.
Dla dużych liczb dzielenie próbne staje się beznadziejnie wolne: przy 30 cyfrach potrzeba by miliardów prób. Ten kalkulator rozpoznaje liczby pierwsze testem Millera-Rabina i rozkłada złożone metodą rho Pollarda, tymi samymi narzędziami, na których opiera się kryptografia.
Częste błędy
- Uznawanie 1 za liczbę pierwszą: z definicji liczba pierwsza ma dokładnie dwa dzielniki, a 1 ma tylko jeden.
- Zatrzymanie się na czynniku, który nie jest pierwszy, jak 360 = 4 · 90: rozkład jest skończony dopiero, gdy wszystkie czynniki są pierwsze.
- Sprawdzanie dzielników powyżej pierwiastka: jeśli n nie ma dzielnika do √n, jest liczbą pierwszą.
Najczęstsze pytania
Jak sprawdzić, czy liczba jest pierwsza?
Wystarczy sprawdzić, że nie dzieli jej żadna liczba pierwsza do jej pierwiastka kwadratowego. Dla 97, z pierwiastkiem około 9,8, wystarczą 2, 3, 5 i 7: żadna jej nie dzieli, więc 97 jest pierwsza.
Do czego służy rozkład na czynniki pierwsze?
Do obliczania NWD i NWW, skracania ułamków i pierwiastków oraz liczenia dzielników. W kryptografii bezpieczeństwo RSA opiera się właśnie na trudności rozkładu ogromnych liczb.
Czym jest funkcja Eulera?
φ(n) liczy, ile liczb od 1 do n nie ma wspólnych czynników z n. Dla liczby pierwszej p wynosi p − 1, dla 360 wynosi 96.
Jak działa to obliczenie
n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ. Liczba dzielników = (a₁ + 1)(a₂ + 1)…(aₖ + 1). Suma dzielników = Π (pᵢ^(aᵢ+1) − 1) / (pᵢ − 1). Funkcja Eulera φ(n) = Π pᵢ^(aᵢ−1)(pᵢ − 1). Metoda: dzielenie próbne przez liczby pierwsze poniżej 1000, deterministyczny test Millera-Rabina i faktoryzacja rho Pollarda w wariancie Brenta.
Powiązane kalkulatory
Rozkład wielomianu na czynniki
Wyłączanie wspólnego czynnika, schemat Hornera, wzory skróconego mnożenia i trójmiany krok po kroku.
Schemat Hornera
Dzieli wielomian przez (x − a) i rozkłada go na czynniki.
NWD i NWW
Największy wspólny dzielnik i najmniejsza wspólna wielokrotność z rozkładem na czynniki pierwsze.
Ułamek okresowy na zwykły
Z ułamka dziesiętnego okresowego na zwykły i ze zwykłego na dziesiętny, z okresem i wyjaśnioną regułą.