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
Sito Eratostenesa
Sito Eratostenesa pozwala utworzyć listę liczb pierwszych. Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
- nie rozumiem ;-; bardzo moim zdaniem ŹLE wytłumaczone(1 głos)
Transkrypcja filmu video
Przedstawię teraz starożytną metodę generowania listy liczb pierwszych do jakiejś granicy n, znaną jako Sito Eratostenesa. Eratostenes urodził się
w 276 r. p. n. e. Metoda ma więc ponad 2200 lat. Jest bardzo prosta i elegancka.
Można jej nauczyć każde dziecko. Powiedzmy np., że chcemy obliczyć
wszystkie liczby pierwsze do 100. Działałoby to tak samo,
gdybyśmy chcieli wyznaczyć te liczby do 10 000 lub miliarda.
Robi się tak: najpierw wszystkie liczby
są niezaznaczone. Szare tło. Zaczynamy od początku. Trafiamy na liczbę niezaznaczoną:
jest to liczba pierwsza. Trafiamy na 2 i mówimy:
to liczba pierwsza, bo niezaznaczona. W drugiej fazie eliminujemy
wszystkie wielokrotności dwóch, bo wiemy, że to liczby złożone. Bum! Eliminujemy wszystkie wielokrotności
dwóch. Czerwień oznacza liczbę złożoną. I powtarzamy.
Przechodzimy do liczby 3. Jest niezaznaczona,
czyli to liczba pierwsza. I eliminujemy wielokrotności trzech. Proste ulepszenie: zauważcie,
że szóstka jest już wykreślona. Zaczynamy eliminować wielokrotności
od kwadratu tej liczby. 3 razy 3 to 9. Zaczynamy od 9 i zaznaczamy
wszystkie wielokrotności 3 jako liczby złożone. Wracamy. Trafiamy na 4.
Zaznaczone – czyli to liczba złożona. Przeskakujemy do piątki.
Niezaznaczona. Liczba pierwsza. 5 razy 5 to 25, idziemy do tego pola. Oznaczamy 25, 30, 35, 40, 45 itd.
To liczby złożone. Idziemy dalej. 7. Wiemy, że to liczba
pierwsza, bo nie została zaznaczona. 7 razy 7 to 49, oznaczamy tę i resztę
wielokrotności 7 powyżej. Złożone. Idziemy dalej. Trafiamy na 11: to liczba pierwsza. Zauważcie: 11 razy 11 jest
większe niż 100, więc możemy się tu zatrzymać.
Moglibyśmy się zatrzymać przy 10, bo wszystkie pozostałe
niezaznaczone liczby są pierwsze. Za jednym zamachem
możemy je zaznaczyć jako pierwsze. I to cały algorytm. Taki prosty. Uogólnijmy to teraz, żeby napisać
program do wykonania sita. Chcąc wyznaczyć liczby pierwsze
do danej granicy n, najpierw stwórzmy główną pętlę.
Dla wszystkich a, od 2 do pierwiastka z n. Zauważcie: zatrzymaliśmy się
przy 10; pokazałem to przy 11. Znaleźliśmy wszystkie liczby pierwsze. Od dwóch do pierwiastka
kwadratowego z n robimy tak: jeśli a jest niezaznaczone… to wiemy, że jest liczbą pierwszą, a kiedy znajdziemy liczbę pierwszą,
zaznaczymy wszystkie wielokrotności a jako liczby złożone. I już. Znajdujecie liczbę pierwszą,
zaznaczacie wielokrotności, wracacie na początek,
zwiększacie a o 1… Jesteśmy przy 2, przechodzimy do 3, potem do 4, 5 itd. A kiedy skończymy, będziemy mieć
wszystkie liczby pierwsze. Zauważcie, że to także jest pętla. Mamy główną pętlę na wypadek
znalezienia liczby pierwszej, ale to odznaczanie wielokrotności
także jest pętlą. Zauważcie, że mamy zagnieżdżoną
pętlę: pętlę w pętli. To jest przykład takiego algorytmu.
Napisałem go w języku JavaScript. Wprowadzam 100. Tu będą wszystkie
liczby pierwsze mniejsze od 100. Wprowadzam 200 i mam
wszystkie liczby pierwsze do 200. A jeśli wprowadzę 850… To będą wszystkie liczby
pierwsze do 850. Poniżej mam ten program z nagraniem, które objaśnia,
jak to zrobiłem.