Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 6: Тест простоты- Введение
- Пройди испытание на тест простоты
- Перебор делителей
- Чем ограничена память компьютера?
- Эффективность алгоритмов
- Уровень 3. Испытание
- Решето Эратосфена
- Уровень 4. Решето Эратосфена
- Тест простоты при помощи решета Эратосфена
- Уровень 5. Перебор делителей при помощи решета Эратосфена
- Теорема о распределении простых чисел
- Скатерть Улама
- Промежутки между простыми числами
- Компромисс времени и памяти
- Итоги (что дальше?)
Теорема о распределении простых чисел
Как оценить количество простых чисел, меньших x? Создатели: Brit Cruise.
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.
Транскрипция к видео
представьте что мы выписали все натуральные числа в виде спирали простые числа выделили голубым фоном а составные оставили на черном и тут возникает интересный вопрос сколько же простых чисел по сравнению со стальными числами у нас здесь давайте взглянем на эту спираль издалека обратите внимание как много голубого цвета в самом центре и как количество голубого цвета плавно уменьшается по мере удаления от центра но в то же время он не заканчивается давайте попробуем представить себе эту картину немного по-другому допустим у нас в центре спирали растет дерево бесконечные высоты с этого дерева падают листья то есть простые числа возле самого дерева их будет много но по мере удаления количество листьев будет уменьшаться именно это и происходит когда мы движемся в сторону больших простых чисел то есть простые числа будут попадаться всегда но в то же время количество попадающихся нам простых чисел будет плавно уменьшаться по мере удаления от центра теперь вернемся к нашему вопросу сколько же простых чисел меньших никого целого числа x если составить таблицу то мы увидим что количество простых чисел постоянно возрастает однако если мы будем продолжать их искать то на нашем пути будет встречаться все меньше и меньше давайте на вертикальной оси будем отмечать количество найденных простых чисел а на оси x отметим количество чисел в поиске если мы взглянем на масштаб в миллиарды чисел то мы увидим что график не будет всегда прямым а напротив он постепенно будет расти хотя и медленно давайте для начала подумаем о плотности распределения простых чисел меньших чем значение x плотностью считается отношение количества простых чисел к общему количеству чисел в поиске в первой сотне натуральных чисел простыми будут 25 то есть плотность простых чисел 25 процентов среди первых десяти тысяч натуральных чисел простыми будут 1229 то есть 12 целых двадцать девять сотых процента в первом миллионе целых чисел простыми будут семь целых восемьдесят четыре сотых процента а среди первых 100 миллионов натуральных чисел простыми будут 5 целых семьдесят шесть сотых процента чем больше мы будем брать интервал тем меньше будет процент на горизонтальной оси этого графика количество чисел в поиске а на вертикальный плотность простых чисел в заданном объеме обратите внимание что с увеличением чисел в поиске количество простых чисел падает поразительно но нужную формулу нам подскажет природа это кривая естественной формы известная как логарифмическая спираль обратите внимание что с каждым новым витком спирали уходят все дальше и дальше от центра невероятно но размер витков логарифмической спирали оказывается связан с плотностью простых чисел обозначим количество витков в греческой буквой фи а расстояние от центра буквой r если изобразить график feat r и уменьшить его то мы увидим что их отношения это натуральный логарифм а это значит что натуральный логарифм расстояние поможет нам найти количество витков обычно график натурального логарифма рисует используя переменные y и x y равен натуральному логарифму x обратите внимание что этот график растет также плавно как уменьшается плотность простых чисел давайте теперь это все немного преобразуем на оси y отметим единицу деленную на натуральный логарифм x уменьшив масштаб мы увидим кривую очень похожую на кривую плотности простых чисел а теперь попробуем совместить один график с другим зелёная кривая это график функции y равен единице деленное на натуральный логарифм x а красная кривая процент простых чисел от 1 до x с уменьшением масштаба они начинают почти совпадать то есть чем больше мы уменьшаем масштаб тем более точно зеленая кривая описывает плотность простых чисел это называется асимптотический закон распределения простых чисел теперь у нас есть формула которая позволяет достаточно точно узнать плотность простых чисел без прямого их подсчета плотность простых чисел на промежутке от 1 до x приблизительно равна единице делённый на натуральный логарифм x например вы хотите узнать чему будет равно в процентах количество простых чисел в промежутке от единицы до 100 триллионов тогда мы единицу делим на натуральный логарифм из 100 триллионов и получаем 3,1 процента сравним это с точным результатом полученным в результате пересчета и здесь у нас три целых и две десятых процента погрешность всего одна десятая процента и чем больше числа мы будем брать тем ближе к нулю будет погрешность при помощи формула распределения простых чисел мы можем посчитать количество простых чисел от 1 до x количество простых чисел это площадь под графиком плотности для простоты можно считать плотность постоянной тогда количество простых чисел будет равняться произведению объема поиска на плотность то есть на количество простых чисел в этом общем количестве чисел другими словами x деленное на натуральный логарифм x это и есть теорема о распределении простых чисел перед вами синий график y равен x деленная на логарифм х а желтая кривая это реальное количество простых чисел от единицы до x мы видим как с уменьшением масштаба кривые сближается почти до полного совпадения и так мы нашли формулу которая позволяет нам приблизительно вычислить количество простых чисел в любом промежутке без прямого пересчета спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них