Rozkład na czynniki pierwsze
Rozłóż liczbę całkowitą na czynniki pierwsze, wypisz jej dzielniki i sprawdź, czy jest liczbą pierwszą.
Działa w całości w twojej przeglądarce. Nic nie jest wysyłane, logowane ani przechowywane.
Rozkład na czynniki pierwsze
2^3 × 3^2 × 5
- Liczba pierwsza?
- nie
- Różne czynniki pierwsze
- 3
- Liczba dzielników
- 24
- Dzielniki
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Każda liczba całkowita większa od 1 jest iloczynem liczb pierwszych i istnieje tylko jeden taki iloczyn – to podstawowe twierdzenie arytmetyki. To narzędzie go znajduje, a z nim wszystko, co z niego wynika: ile dzielników ma liczba i jakie to są dzielniki.
Jak to działa
Dzielenie próbne, ze skrótem: po wyciągnięciu 2 i 3 każda pozostała liczba pierwsza leży tuż obok wielokrotności sześciu, z jednej lub z drugiej strony, więc kandydaci idą co sześć, a nie co dwa. Co przetrwa to sito, jest liczbą pierwszą i wchodzi jako ostatni czynnik.
Dzielniki buduje się z rozkładu, a nie sprawdzając każdą liczbę aż do n. Liczba zapisana jako 2³ × 3² × 5 ma (3+1) × (2+1) × (1+1) = 24 dzielniki, a każdy z nich to wybór, ile razy wziąć każdą liczbę pierwszą – więc gdy rozkład jest znany, wypisanie ich nic nie kosztuje.
Granicą jest bilion. Dzielenie próbne dochodzi co najwyżej do pierwiastka kwadratowego z liczby, czyli tam do miliona kroków: szybko. Powyżej liczba, która okazałaby się iloczynem dwóch dużych liczb pierwszych, zostawiłaby stronę ładującą się przez minutę, więc narzędzie odmawia.
Przykłady
| Przypadek | Dane wejściowe | Wynik |
|---|---|---|
| Liczba z wieloma dzielnikami | 360 | 2³ × 3² × 5: 24 dzielniki |
| Liczba pierwsza | 97 | 97: liczba pierwsza, 2 dzielniki |
| Potęga dwójki | 1024 | 2¹⁰: 11 dzielników |
Najczęściej zadawane pytania
Dlaczego zaczyna się od 2, a nie od 1?
Bo 1 nie ma rozkładu na czynniki pierwsze, a nazwanie jej liczbą pierwszą zniszczyłoby jednoznaczność, na której opiera się cały ten dział: gdyby 1 była pierwsza, 6 byłoby 2 × 3 i 1 × 2 × 3, i 1 × 1 × 2 × 3, i nie byłoby już jednej odpowiedzi. Zero jest jeszcze gorsze: dzieli je każda liczba.
Ile dzielników ma liczba?
Dodaj jeden do każdego wykładnika w rozkładzie i wymnóż. 360 to 2³ × 3² × 5, więc 4 × 3 × 2 = 24. Liczba pierwsza ma 2 – samą siebie i 1 – a kwadrat liczby całkowitej ma ich zawsze nieparzyście wiele, bo jeden z dzielników jest swoją własną parą.
Dlaczego jest górna granica?
Dzielenie próbne jest dokładne i szybkie, dopóki nie przestaje być szybkie. Najgorszy przypadek to iloczyn dwóch liczb pierwszych bliskich pierwiastkowi kwadratowemu, a tutejsza granica leży tam, gdzie taki przypadek wciąż mieści się w czasie ładowania strony. Odmowa mówi ci, co się stało; przekroczony limit czasu nie mówi nic.
Czy tak łamie się klucze szyfrujące?
Nie – i w tym cały sens. RSA opiera się na trudności rozłożenia liczby mającej kilkaset cyfr; dzielenie próbne takiej liczby trwałoby dłużej, niż istnieje wszechświat. Lepsze metody istnieją, ale wciąż nie zbliżają się do celu nawet z daleka – i dlatego ten schemat działa.
Warto wiedzieć
- Dzielniki są wypisywane w całości, jeśli jest ich najwyżej sześćdziesiąt cztery; powyżej pokazywana jest tylko ich liczba, bo strony z dziewięciuset liczbami nikt nie czyta.
Wszystkie narzędzia z kategorii Matematyka