If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Metoda próbnych dzieleń

Określ problem

Mamy zbudować maszynę, która będzie w stanie udzielić prostej odpowiedzi tak lub nie, na pytanie, czy dana liczba całkowita n, jest liczbą pierwszą?
Zastanówmy się nad tym, co musiałoby się znajdować w takiej maszynie, aby spełniła swoją funkcję. Maszyny mogą tylko wykonywać określone kroki w oparciu o zdefiniowane instrukcje, nazywamy to algorytmem. Dla rozgrzewki, spróbujmy odszyfrować jaki algorytm znajduje się wewnątrz Twojej głowy. Odpowiedz na następujące pytanie: czy 49 jest liczbą pierwszą?
Nie? Jak to zrobiłeś? Prawdopodobnie odszukałeś dzielnik liczby 49, który jest większy od 1 i mniejszy od 49. Jeśli nie zapamiętałeś tabliczki mnożenia, z pewnością musiałeś wykonać poniższe kroki:
  • Czy 49 dzieli się przez 2?     NIE
  • Czy 49 dzieli się przez 3?     NIE
  • Czy 49 dzieli się przez 4?     NIE
  • Czy 49 dzieli się przez 5?     NIE
  • Czy 49 dzieli się przez 6?     NIE
  • Czy 49 dzieli się przez 7?    TAK
Znaleźliśmy dzielnik liczby 49 (7), który jest dowodem, że liczba 49 jest złożona.

Określenie punktu granicznego

Gdybym zapytał, czy 2971215073 jest liczbą pierwszą?
Jeszcze sprawdzasz? Ja, po pierwszych kilku tysiącach prób, w dalszym ciągu nie odnalazłem dzielnika. Podstawowe pytanie jakie się nasuwa to kiedy możemy przestać sprawdzać, czy n jest liczbą pierwszą? (nazwijmy to naszym punktem granicznym). Jako pierwsze, ustalmy, że naszym punktem granicznym musi być n-1 (ponieważ n dzieli się przez n). Gdybyśmy sprawdzili wszystkie dzielniki, aż do 2971215072, albo znaleźlibyśmy dzielnik (co równoważne byłoby z tym, że liczba n jest złożona), albo nie (co dowiodłoby, że n jest liczbą pierwszą).

Określenie jeszcze lepszego punktu granicznego

Powyższy schemat z pewnością by zadziałał, lecz czy możemy przesunąć nasz punkt graniczny aby zaoszczędzić czas? Pamiętaj, że w dalszym ciągu poszukujemy pierwszego (najmniejszego) dzielnika. Zdarza się, że czasami najmniejszym dzielnikiem będzie 2, jednak czasami może być to o wiele większa liczba. To nasuwa nam konkretne pytanie: jak duży może być najmniejszy dzielnik?
Pamiętajmy, że każda złożona liczba całkowita składa się z dwóch lub więcej liczb pierwszych n= P * P …
P jest największe gdy n ma dokładnie dwa dzielniki, które są sobie równe. Pojęcie to znane jest szerzej jako liczba kwadratowa dla przykładu 9 (9 = 33) lub 49 (49 = 77). W celu pozbycia się najgorszego ze scenariuszy, określmy naszą granicę jako pierwiastek z n!
Przekonaj siebie, że: jeśli nie znajdziesz dzielnika liczby n po sprawdzeniu liczby kwadratowej n, to liczba n musi być liczbą pierwszą. Spróbuj sobie to udowodnić (dowód znajdziesz na dole tego wpisu)

Przykładowy algorytm dzielenia

No cóż, jesteśmy gotowi by pójść krok dalej Zacznijmy od opisania naszego algorytmu otwartym tekstem po polsku:
  • Zanotuj zadaną liczbę naturalną n
  • Dla każdej liczby naturalnej x z przedziału {2 ... sqrt(n)} sprawdź, czy x jest dzielnikiem n
  • Jeśli znalazłeś dzielnik n, n jest liczbą złożoną OR ELSE n jest liczbą pierwszą
Jeśli znasz się na programowaniu, możesz otworzyć CSscratchpad i spróbować zakodować tą funkcję. Jeśli masz z tym problem, możesz przejść do następnego kroku, gdzie przedstawiłem działającą wersje abyś miał od czego zacząć. (Dla Twojej informacji, możesz wykonać tą lekcję pomijając programowanie).

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.