Główna zawartość
Informatyka
Kurs: Informatyka > Jednostka 2
Lekcja 6: Test pierwszości- Wprowadzenie
- Wyzwanie: test pierwszości
- Metoda próbnych dzieleń
- Czym jest pamięć komputera?
- Wydajność algorytmu
- Poziom 3: Wyzwanie
- Sito Eratostenesa
- Poziom 4: Sito Eratostenesa
- Test pierwszości z sitem Etastotenesa
- Poziom 5: Próba podziału za pomocą sita
- Twierdzenie o liczbach pierwszych
- Spirala Ulama liczb pierwszych
- Odległość pomiędzy liczbami pierwszymi
- Kompromis czasu i pamięci
- Podsumowanie (co dalej?)
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
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