С какой вероятностью число — простое?

Давненько у нас не было понедельничной рубрики о простых числах! Исправляемся.
Сегодня принесли вам Теорему о распределении простых чисел.

Оказывается, если взять конкретный отрезок, то можно примерно оценить, сколько простых чисел на нём содержится. Конкретно теорема звучит так: на отрезке от 1 до n содержится около n ÷ ln(n) простых чисел. При этом чем больше n, тем точнее эта формула описывает их количество.

Формальное доказательство теоремы непростое. Но это не мешает нам проверить, как она работает! Посмотрим на нескольких отрезках:
• На отрезке от 1 до 10 формула обещает 10 ÷ ln10 ≈ 4.3 простых числа. В действительности их 4 штуки: 2, 3, 5, 7. Доля ошибки равна (4.3-4) ÷ 4 = 0.075, или 7.5%. Обратите внимание: здесь прогнозируемое количество простых чисел больше реального.
• На отрезке от 1 до 100 формула обещает 100 ÷ ln100 ≈ 21.7 простых числа. По факту же их 25. Доля ошибки равна (25-21.7) ÷ 25 = 0.132, или 13.2%. Хм, во-первых, на этом отрезке прогноз уже ниже реального количества — видим, что оценка может отклоняться в любую сторону. Во-вторых, стало хуже! Продолжим смотреть и надеяться, что дальше это исправится.
• На отрезке от 1 до 1000 по формуле ожидаем 1000 ÷ ln1000 ≈ 144.8 простых числа, а в действительности их 168, они выписаны на картинке ниже. Посчитаем ошибку: (168-144.8) ÷ 168 = 0.138 или 13.8%. Стало ещё хуже, но скачок был уже не такой драматичный. Обещаем, дальше всё наладится. :)