Rozkład na czynniki pierwsze

Rozkład liczby na czynniki pierwsze i sprawdzenie, czy jest pierwsza

Każdą liczbę całkowitą od 2 wzwyż można zapisać jako iloczyn liczb pierwszych w dokładnie jeden sposób (z dokładnością do kolejności czynników): to podstawowe twierdzenie arytmetyki. 360 = 2³ × 3² × 5, 1001 = 7 × 11 × 13, a 97 w ogóle się nie rozkłada: jest liczbą pierwszą. Ten kalkulator podaje rozkład, od razu mówi, czy liczba jest pierwsza czy złożona, i pokazuje rozkład metodą kreski dokładnie tak, jak zapisuje się go na lekcji.

Rozkład na czynniki to klucz do wielu obliczeń: skracania ułamków, wyznaczania NWD i NWW, liczenia dzielników, upraszczania pierwiastków. Przydaje się uczniom klas 4 do 8 i liceum, nauczycielom przygotowującym sprawdziany, osobom szykującym się do egzaminu ósmoklasisty i olimpiad, a także wszystkim ciekawym kryptografii: bezpieczeństwo RSA opiera się na tym, że bardzo duże liczby trudno rozłożyć na czynniki.

1. Wpisz liczbę

   Wpisz liczbę całkowitą w polu „Liczba całkowita do rozłożenia” (od 2, maksymalnie 18 cyfr). Spacje i separatory tysięcy są pomijane, więc 600 851 475 143 działa bez zmian. Przyciski „Przykłady:” wczytują gotowe przykłady.

2. Odczytaj werdykt

   Etykieta pokazuje „Liczba pierwsza” albo „Nie jest pierwsza: liczba złożona”, a pod nią pojawia się rozkład z wykładnikami (360 = 2³ × 3² × 5) i postać rozwinięta. Przycisk „Kopiuj” umieszcza 2^3 × 3^2 × 5 w schowku.

3. Poznaj własności

   Karty „Własności arytmetyczne” podają τ(n), σ(n), φ(n), liczbę różnych czynników pierwszych ω(n) i czynników z krotnością Ω(n), informację, czy n jest kwadratem liczby naturalnej, sumę dzielników właściwych oraz poprzednią i następną liczbę pierwszą (do 10¹²).

4. Sprawdź ręcznie

   Tabela „Rozkład metodą kreski (kolejne dzielenia)” powtarza każdy krok (360 ÷ 2 = 180…) aż do ilorazu 1, a „Wszystkie dzielniki” wypisuje dzielniki rosnąco, wyróżniając dzielniki pierwsze.

Metoda: podstawowe twierdzenie arytmetyki i wzory

Dla liczby całkowitej n ≥ 2 rozkład zapisujemy jako n = p1a1 × p2a2 × … × pkak. Otrzymujemy go, dzieląc przez najmniejszy czynnik pierwszy tak długo, jak się da; dzielniki wystarczy sprawdzać do √n, bo liczba złożona zawsze ma czynnik pierwszy nie większy niż jej pierwiastek.

Dla dużych liczb narzędzie łączy trzy etapy: dzielenie próbne przez liczby pierwsze do 10 000, deterministyczny test Millera-Rabina rozpoznający liczby pierwsze oraz algorytm rho Pollarda (wariant Brenta) rozbijający pozostałe czynniki złożone. Wszystkie obliczenia są wykonywane na dokładnych liczbach całkowitych, bez zaokrągleń.

• p₁ < p₂ < … < p_k: różne czynniki pierwsze w kolejności rosnącej; ich liczbę oznacza się ω(n).
• a_i: wykładnik (krotność) p_i; suma a₁ + … + a_k to Ω(n), liczba czynników pierwszych liczonych z powtórzeniami.
• τ(n) = (a₁ + 1)(a₂ + 1)…(a_k + 1): liczba dzielników, bo każdy dzielnik wybiera dla każdego p_i wykładnik od 0 do a_i.
• σ(n) = ∏ (p_i^a_i+1 − 1) / (p_i − 1): suma wszystkich dzielników; s(n) = σ(n) − n mówi, czy liczba jest doskonała, obfita czy deficytowa.
• φ(n) = n × ∏ (1 − 1/p_i): funkcja Eulera, czyli ile liczb od 1 do n jest względnie pierwszych z n.
• Kwadrat liczby naturalnej: n jest kwadratem wtedy i tylko wtedy, gdy wszystkie a_i są parzyste; wtedy √n = ∏ p_i^a_i/2, na przykład √1024 = 2⁵ = 32.

Przykłady rozkładu na czynniki pierwsze

Do czego służy rozkład na czynniki pierwsze?

• Skracanie ułamków: 84/360 = (2² × 3 × 7)/(2³ × 3² × 5) = 7/30 po skreśleniu wspólnych czynników 2² × 3 = 12.
• Wspólny mianownik: NWW liczb 360 i 84 wynosi 2520, to najmniejszy wspólny mianownik do dodania 1/360 i 1/84.
• Upraszczanie pierwiastków: √360 = √(2² × 3² × 10) = 2 × 3 × √10 = 6√10: każdą parę jednakowych czynników wyłączamy przed pierwiastek.
• Liczenie i wypisywanie dzielników: przydatne w zadaniach o podziale (ustawienie 360 krzeseł w równych rzędach: 24 możliwe układy rzędy × kolumny) i w pracach domowych z podzielności.
• Kryptografia i łamigłówki: RSA opiera się na trudności rozkładu; słynne zadanie 3 z Project Euler pyta o największy czynnik pierwszy liczby 600 851 475 143, czyli 6857.

Częste błędy

• Dzielenie przez liczbę, która nie jest pierwsza: dzielenie 360 przez 4 lub 6 daje poprawny iloraz, ale niepełny rozkład; dzielimy tylko przez 2, 3, 5, 7, 11, 13…
• Uznawanie 1 za liczbę pierwszą: 1 ma tylko jeden dzielnik i nigdy nie występuje w rozkładzie.
• Mylenie 2³ z 2 × 3: 2³ = 2 × 2 × 2 = 8, a 2 × 3 = 6; wykładnik mówi, ile razy powtarza się czynnik.
• Uznawanie liczby za pierwszą, bo „tak wygląda”: 51 = 3 × 17, 91 = 7 × 13 i 1001 = 7 × 11 × 13 są złożone; zawsze sprawdzaj do pierwiastka.

Wszystkie obliczenia odbywają się lokalnie w Twojej przeglądarce, na dokładnej arytmetyce całkowitej (BigInt): żadna liczba nie jest wysyłana ani zapisywana. Ograniczenia: maksymalnie 18 cyfr; sąsiednie liczby pierwsze są pokazywane do 10¹², lista dzielników do 1000 dzielników, a tabela dzieleń do 40 czynników pierwszych liczonych z krotnością.