Kalkulator rozkładu na czynniki pierwsze
Podaj liczbę całkowitą, a zapiszemy ją jako iloczyn liczb pierwszych, np. 360 = 2³ × 3² × 5.
Wynik
2³ × 3² × 5Rozkład na czynniki pierwsze
- Liczba różnych czynników pierwszych
- 3
- 2 występuje 3 razy
- 3 występuje 2 razy
- 5 występuje 1 razy
Dane wejściowe
- Liczba całkowita
- 360
Jak to obliczyć
Dziel przez 2, a następnie 3, 5, 7… (do 100 000), dopóki to możliwe.
Wynik
Rozkład na czynniki pierwsze
- Liczba różnych czynników pierwszych
- 3
Jak to obliczyć
- Dziel przez 2, a następnie 3, 5, 7… (do 100 000), dopóki to możliwe.
- Jeśli duża reszta nie jest pierwsza, szukaj czynnika metodą rho Pollarda.
- Każdy czynnik sprawdzamy testem pierwszości Millera–Rabina.
- Czas obliczeń jest ograniczony; narzędzie poinformuje, jeśli go zabraknie.
Przykład
360 = 2 × 180 = 2 × 2 × 90 = … = 2³ × 3² × 5.
Warto wiedzieć
- Maksymalnie 30 cyfr. Iloczyn dwóch bardzo dużych liczb pierwszych może zostać odrzucony.
- Powyżej około 25 cyfr czynnik jest „prawdopodobnie pierwszy”, a nie dowiedziony.
Kiedy użyć
- Użyj rozkładu do skracania ułamków lub obliczania NWW.
- Sprawdź, czy dana liczba jest pierwsza.
Częste pytania
Czym jest rozkład na czynniki pierwsze?
To zapis liczby całkowitej jako iloczynu liczb pierwszych, np. 360 = 2³ × 3² × 5.
Jak znajdowane są czynniki pierwsze?
Narzędzie najpierw dzieli przez małe liczby pierwsze, a dla dużej reszty używa algorytmu szukania czynników i testu pierwszości.
Czy bardzo duży czynnik zawsze jest udowodniony jako pierwszy?
Nie. Dla bardzo dużych czynników wynik testu Millera–Rabina może oznaczać „prawdopodobnie pierwszy”, a nie formalny dowód.