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
Twierdzenie o liczbach pierwszych
Jak możemy oszacować liczbę liczb pierwszych do x? Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Wypisaliśmy wszystkie
liczby całkowite w spirali. Liczby pierwsze zaznaczyliśmy
na niebiesko. Złożone są na czarnym tle. Można zadać ciekawe pytanie: „Ile jest liczb pierwszych
w stosunku do złożonych?”. Najpierw spójrzmy
z większej odległości. Koloru liczb pierwszych
jest więcej pośrodku, stopniowo go ubywa, ale wydaje się,
że on nigdy nie zniknie. Lubię o tym myśleć tak: pośrodku rośnie
nieskończenie wysokie drzewo. Spadające z niego liście
to liczby pierwsze. Nieprzewidywalnie
rozproszone na ziemi. Przy pniu jest gęsto. Odchodząc od niego,
znajdujemy mniej liści, ale jakieś zawsze są. Tak samo dzieje się, gdy patrzymy
na rosnące liczby całkowite. Zawsze znajdujemy liczby pierwsze, ale stopniowo ich liczba maleje,
im dalej patrzymy. Wróćmy do pytania.
Ile jest liczb pierwszych mniejszych od danego całkowitego x? Jeśli sporządzimy tabelę, zobaczymy,
że liczb pierwszych stale przybywa. Chociaż, gdy szukamy dalej,
znajdujemy ich coraz mniej. Zaznaczmy na osi pionowej ilość
znajdowanych liczb pierwszych, a obszar poszukiwań, x,
na osi poziomej. Cofamy się, żeby zobaczyć
miliardy liczb. Krzywa nigdy nie staje się płaska. Zawsze się wznosi, chociaż stopniowo. Najpierw pomyślmy o gęstości
liczb pierwszych mniejszych od danego całkowitego x.
Wyznaczymy tę gęstość, dzieląc ilość znalezionych liczb
przez wielkość obszaru poszukiwań. W pierwszej setce liczb całkowitych
jest 25 liczb pierwszych: 25%. W pierwszych 10 000 liczb całkowitych znajdujemy 1229 liczb pierwszych,
czyli 12,29%. W pierwszym milionie liczb całkowitych
7,84% to liczby pierwsze. A pierwsze 100 mln liczb całkowitych
zawiera 5,76% liczb pierwszych. Szukamy dalej, a gęstość
nadal spada, chociaż prędkość tego opadania
zmniejsza się. Obszar poszukiwań jest na osi poziomej,
gęstość liczb pierwszych - na pionowej. Liczb pierwszych jest coraz mniej w stosunku do wszystkich
liczb naturalnych. Co zdumiewające, znajdujemy
ten wzór w przyrodzie. W galaktykach, układzie burz, kwiatach, a nawet
w naszych organizmach, bo to projekt
najmniejszego oporu, znany jako spirala logarytmiczna. Zwróćcie uwagę, że spirala
coraz bardziej oddala się od środka. Niesłychane: prędkość obrotu
spirali logarytmicznej do gęstości liczb pierwszych
odnosi się następująco: mamy liczbę obrotów,
nazwijmy ją φ. A odległość od środka
niech nazywa się r. Jeśli zrobimy wykres φ w zależności
od r i spojrzymy z daleka, zobaczymy, że jest związek
zgodnie z logarytmem naturalnym. To oznacza, że logarytm
naturalny odległości ma związek z liczbą obrotów. Wykres logarytmu naturalnego zwykle sporządzamy
z pomocą zmiennych y i x, gdzie y równa się ln(x). Zauważcie, że wykres
kształtuje się tak samo: gęstość liczb pierwszych
stopniowo maleje. Ostatni krok: odwrócić to wyrażenie. Niech na na osi Y będzie
„1 podzielić przez ln(x)”. Patrząc z perspektywy,
zobaczymy taką samą krzywą wygenerowaną z nałożenia
gęstości liczb pierwszych. Potwierdźmy to,
nakładając wykresy na siebie. Na zielono – wykres
y równa się 1 przez ln(x) Na czerwono – wykres
gęstości liczb pierwszych aż do x. Cofając się, widzimy,
że zbliżają się do siebie. Im dalej, tym dokładniejsze stają się
zielone wartości szacunkowe. Jest to znane jako asymptotyczne prawo
rozmieszczenia liczb pierwszych. Teraz mamy wzór,
który dokładnie poda nam gęstość liczb pierwszych,
bez obliczania. Gęstość liczb pierwszych
aż do danej liczby całkowitej x to, w przybliżeniu, 1 przez ln(x). Chcecie wyznaczyć
gęstość liczb pierwszych między 1 a 100 bilionów. Proste. 1 podzielić przez logarytm naturalny
ze stu bilionów to 3,1%. Porównajcie to z rzeczywistym
wynikiem liczenia wszystkich liczb pierwszych,
czyli 3,2%. Różnica wynosi 0,1%. Gdy sprawdzamy coraz większe liczby, różnica zbliża się do zera. Możemy użyć tego wzoru na gęstość liczb pierwszych, by oszacować ich liczbę do x. Liczba liczb pierwszych do x
to x pomnożone przez gęstość, albo x podzielić przez ln (x). To jest twierdzenie
o liczbach pierwszych. Oto wykres y równa się x
przez ln(x), na niebiesko, a na żółto zaznaczono rzeczywisty
wynik liczenia liczb pierwszych. Cofając się, zauważmy, że w końcu
wykresy nałożą się na siebie. I już. Mamy wzór, który mówi nam
w przybliżeniu, ile jest liczb pierwszych do danej
wartości, bez potrzeby liczenia. Np. mamy określić, ile jest liczb
pierwszych mniejszych niż 100 bln. 100 bln dzielone przez logarytm
naturalny ze stu bilionów równa się 3,1 bln. Porównajcie to
z wynikiem liczenia: 3,2 bln. Dokładność przekracza 99,99%. nawet w tej stosunkowo
małej skali. Podsumujmy: przy danym obszarze
poszukiwań do liczby całkowitej x, gęstość liczb pierwszych
to, około 1 przez ln(x). A ilość tych liczb to w przybliżeniu
x podzielić przez ln(x). To jest twierdzenie
o liczbach pierwszych.