Informatyka · Algorytmy i złożoność
Jak podzielić 48 i 18 bez reszty?
Masz 48 naklejek i 18 kart. Chcesz zrobić jednakowe zestawy, bez żadnych resztek. Szukasz największej liczby zestawów. Potem zmienimy pytanie: które liczby do 30 są pierwsze?
- Najpierw przewidź
- Potem sprawdź
- Na końcu wyjaśnij
Po tej lekcji: Obliczysz NWD i NWW oraz wyznaczysz liczby pierwsze sitem.
Zakres podstawowy · materiał otwarty
NWD: największy wspólny dzielnik
Dzielnik dzieli liczbę bez reszty. Dla 18 dzielniki to 1, 2, 3, 6, 9, 18. Wspólne dzielniki 48 i 18 to 1, 2, 3, 6, więc NWD wynosi 6. Euklides skraca pracę: zamiast pary (48, 18) bierze (18, 48 % 18), czyli (18, 12). Potem (12, 6), a na końcu (6, 0). Gdy druga liczba jest zerem, pierwsza jest wynikiem. Reszta jest zawsze mniejsza od dzielnika — dlatego ten proces się kończy.
Sprawdź w działaniu
Podziel pasek na równe kawałki
Zmieniaj dwie liczby. Zobacz, ile pełnych kawałków mieści się w pierwszym pasku i jaka reszta zostaje. Przed krokiem spróbuj ją obliczyć.
Liczby pierwsze: dokładnie dwa dodatnie dzielniki
Liczba pierwsza jest większa od 1 i ma tylko dzielniki 1 oraz samą siebie. 2 jest pierwsza; 1 nie jest. Sito Eratostenesa znajduje wiele liczb pierwszych naraz. Zostawiasz najmniejszą niewykreśloną liczbę p, a wykreślasz jej wielokrotności od p². Mniejsze wielokrotności wykreśliły już mniejsze liczby pierwsze. Wystarczy przesiać p do pierwiastka z granicy.
Prześledź kod: NWD dwóch liczb
a, b = 18, 12
while b != 0:
a, b = b, a % b
print(a)Co robi ten kod?
Pary zmieniają się: (18,12), (12,6), (6,0). Wynik to 6. Równoczesne przypisanie korzysta ze starych wartości obu zmiennych. W sicie dla 20 skreśl wielokrotności 2, potem 3; zostaje 2,3,5,7,11,13,17,19.
NWW: kiedy znów spotkają się cykle?
Dzwonek A dzwoni co 6 minut, B co 8. Razem zadzwonią po 24 minutach: to najmniejsza wspólna wielokrotność. Dla dodatnich a,b: NWW(a,b) = a * b // NWD(a,b). Dla 6 i 8: 48 // 2 = 24. W kodzie można najpierw podzielić przez NWD i dopiero mnożyć.
Ćwiczenie z pomocą · samodzielna praca
Twoja próba — bez punktów
Wypisz liczby pierwsze od 2 do wczytanego n (2–50), oddzielone spacjami. Dla 10 wynik to 2 3 5 7. Następnie ręcznie znajdź NWD(42, 30).
Zapisz dane, kolejne decyzje i wynik. Sprawdź go w symulacji lub swoim programie.
? Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź
Zacznij od wypisania danych i ustalenia, czego szukasz.
Krok 2 — pokaż podpowiedź
Wykonaj ręcznie pierwszy krok zgodnie z regułą z lekcji.
Krok 3 — pokaż podpowiedź
Sprawdź wynik inną metodą i wyjaśnij, dlaczego algorytm się zatrzyma.
Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.
Podsumowanie
Co warto zapamiętać
- NWD to największy wspólny dzielnik.
- NWW(a,b)=a//NWD(a,b)*b dla dodatnich a,b.
- Sprawdź także liczby równe i dzielące się bez reszty.
Po zalogowaniu zobaczysz dodatkowe lekcje i materiały oznaczone jako rozszerzenie. Podstawowe quizy i zadania pozostają dostępne w biurku.
Dalej na swoim koncie
Rozgrzewki, quiz i zadania są w biurku ucznia.
Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.
Zaloguj się →