Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 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
Test pierwszości z sitem Etastotenesa
Próba zoptymalizowania testu pierwszości za pomocą Sita Erastotenesa. Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Podsumujmy: to, czy n jest liczbą pierwszą,
sprawdzamy metodą próbnych dzieleń. Tu jest pierwiastek
kwadratowy z n, a tu jest 3. Zaczynając od trzech,
przeskakujemy o dwa pola, aż do pierwiastka z n. Sprawdzamy, czy każda liczba
po drodze dzieli n. Do tej pory ludzie starali się
zmniejszać liczbę kroków, zaczynając później albo wydłużając te kroki. Zatrzymam się przy tym. Zastanówmy się, jaki jest
idealny przypadek dla algorytmu próbnych dzieleń. Co najlepszego możemy
w tej sprawie wymyślić? Pamiętajcie, każda liczba n
ma rozkład na czynniki pierwsze. Powiedzmy,
że tu jest pierwiastek z n. Musimy stawać
tylko na liczbach pierwszych. Tak byłoby najlepiej. Zatrzymując się
tylko na liczbach pierwszych, w końcu znajdziemy dzielnik n. Pytanie: jak wydajna jest ta metoda? Wydaje się, że mamy
doskonałe rozwiązanie. Gdybyśmy napisali nowy algorytm, który najpierw stosowałby sito… Niech oblicza,
czy n jest liczbą pierwszą. Jeśli zastosujecie sito i wygenerujecie
długą serię liczb pierwszych, a potem zastosujecie
metodę próbnych dzieleń… z użyciem tej listy liczb pierwszych… Naszą metodą będziecie przechodzić
tylko przez liczby pierwsze. Do pierwiastka z n,
jakąkolwiek ma wartość. Co jest z tym nie tak? Możemy wizualizować złożoność czasową
albo liczbę wykonanych kroków. Pamiętajcie, wziąłem ten algorytm i dodałem licznik kroków
do każdej pętli, więc mamy… Powiedzmy, że „STEP ++”
oznacza krok plus jeden. W tej pętli
także jest licznik kroków. Step ++. To są stałe operacje,
które sprawdzają i oznaczają liczby. W każdej pętli mamy licznik kroków. Teraz porównanie. Po lewej stronie jest metoda
próbnych dzieleń, pośrodku algorytm, za pomocą sita generujący
wszystkie liczby pierwsze do n, a po prawej jest propozycja,
w której stosujemy sito, by generować liczby pierwsze
do pierwiastka z n i tylko do nich stosujemy
metodę próbnych dzieleń. Zobaczmy, co będzie
przy małych danych wejściowych. Jak widzicie, z początku
sito zajmuje wiele kroków. Nawet zmodyfikowana wersja
po prawej stronie jest wolniejsza od metody
próbnych dzieleń. Gdy wprowadzamy większe liczby,
liczba kroków rośnie jeszcze szybciej. Zapomnijmy o tym środku
i porównajmy metodę próbnych dzieleń z sitem do pierwiastka z n
i próbnymi dzieleniami. Zobaczymy, że stara metoda próbnych
dzieleń jest znacznie wydajniejsza. Liczba kroków w sicie
do pierwiastka z n plus metoda próbnych dzieleń
rośnie znacznie szybciej. Zatem to żadne ulepszenie. Poniżej jest program,
którego użyłem do tego porównania. Oraz nagranie wyjaśniające,
jak to zrobiłem. Pewnie się zastanawiacie: „A gdybyśmy obliczyli
liczby pierwsze z wyprzedzeniem?”. Najpierw trzeba byłoby
stworzyć tablicę liczb pierwszych i przechowywać ją
na twardym dysku. Wtedy nasz algorytm stosowałby
tylko metodę próbnych dzieleń, skacząc wyłącznie
po liczbach pierwszych, bo korzystałby z listy. Nasz wykaz może zawierać wszystkie liczby pierwsze
do 20 cyfr, a nawet do 100. Dlaczego tego nie robimy? Problemem jest ograniczenie pamięci. Sporządzając tabele liczb,
czym zajmiemy się później… Powiedzmy, że robimy to ręcznie. Obliczamy, że 5 to liczba pierwsza, zapisujemy piątkę na kartce
i przechowujemy w szafce. Później uzyskujemy 7,
wkładamy tę liczbę do szafki, 9… przepraszam, 11, do szafki, Uzyskamy szafkę
pełną liczb pierwszych. To nasza… tablica liczb pierwszych. Jak duża musiałaby być ta szafka, by pomieścić wszystkie
liczby pierwsze do 20 albo 100 cyfr? Czy moglibyśmy przechować
taką tabelę na twardym dysku? Żeby zrozumieć,
dlaczego nie jest to możliwe, powinniśmy zbadać dokładniej, jak duża musi być
tablica liczb pierwszych i jakie jest ograniczenie wielkości współczesnego, a nawet przyszłego
sprzętu komputerowego.