Rozkład na czynniki pierwsze i dzielniki
Rozkładanie N na potęgi liczb pierwszych i zliczanie dzielników
Rozkład na czynniki pierwsze i dzielniki to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Rozkład liczby N
Każda liczba całkowita większa od 1 jest jednoznacznym iloczynem liczb pierwszych. Znalezienie tego rozkładu, czyli jej rozkładu na czynniki pierwsze, otwiera drogę do rozwiązania wielu problemów teorii liczb. 🧩
Idea dzielenia próbnego
Należy wyodrębnić najmniejszą liczbę pierwszą dzielącą n, podzielić przez nią n i powtarzać tę operację. To proste dzielenie próbne rozkłada n aż do uzyskania 1.
Pętla do pierwiastka
Należy sprawdzać dzielniki i, dopóki i*i pozostaje mniejsze lub równe n. Powyżej pierwiastka kwadratowego może pozostać co najwyżej jeden czynnik pierwszy.
while i * i <= n:
...Wyodrębnianie kolejnych czynników
Dopóki i dzieli n, należy kontynuować dzielenie i zapisywać i. W ten sposób przechwytuje się pełną potęgę tej liczby pierwszej przed przejściem dalej.
while n % i == 0:
factors.append(i)
n //= iPozostały czynnik pierwszy
Po zakończeniu pętli, jeśli n nadal jest większe od 1, samo jest czynnikiem pierwszym większym od pierwiastka kwadratowego. Należy dodać je raz.
if n > 1:
factors.append(n)Pełna procedura
Wspólnie daje to rozkład na czynniki w czasie O(sqrt n), zwracając każdą liczbę pierwszą z pełną krotnością i we właściwej kolejności.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fGrupowanie w potęgi
Przy zliczaniu dzielników potrzebna jest każda liczba pierwsza wraz z jej wykładnikiem, na przykład 2^3 zamiast 2,2,2. Obiekt Counter przejrzyście zlicza powtórzenia.
from collections import Counter
exp = Counter(factorize(n))Wzór na liczbę dzielników
Jeśli n jest równe p1^a razy p2^b, liczba dzielników wynosi (a+1) razy (b+1). Każdy wykładnik otrzymuje jedną dodatkową możliwość.
Policz dzielniki
Pomnóż o jeden każdy wykładnik występujący przy liczbach pierwszych. Otrzymasz całkowitą liczbę dzielników bez wypisywania ich po kolei.
count = 1
for e in exp.values():
count *= (e + 1)Suma dzielników
Powiązany wzór oblicza sumę dzielników za pomocą szeregu geometrycznego dla każdej liczby pierwszej. Jego znajomość pomaga w zadaniach dotyczących liczb doskonałych i problemów aliquotowych.
Przyspiesz obliczenia za pomocą sita
Przy wielu rozkładach na czynniki warto wstępnie obliczyć najmniejszy czynnik pierwszy każdej liczby za pomocą sita. Następnie każde zapytanie można rozłożyć na czynniki w log n krokach.
Szybkie sprawdzenie
Zastosuj wzór na liczbę dzielników do konkretnej liczby.
Podsumowanie
Można teraz rozłożyć N na czynniki metodą próbnych podziałów w czasie O(sqrt n), uwzględnić pozostałą liczbę pierwszą, pogrupować wykładniki i policzyć dzielniki za pomocą wzoru iloczynowego. ✅
Często zadawane pytania
Czy lekcja „Rozkład na czynniki pierwsze i dzielniki” jest bezpłatna?
Tak — pełny tekst „Rozkład na czynniki pierwsze i dzielniki” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Rozkład na czynniki pierwsze i dzielniki”?
Rozkładanie N na potęgi liczb pierwszych i zliczanie dzielników Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Rozkład na czynniki pierwsze i dzielniki”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- NWD, NWW i algorytm Euklidesa
- Testowanie pierwszości do sqrt(n)
- Sito Eratostenesa
- Rozkład na czynniki pierwsze i dzielniki