Теорема о простых числах - это теорема из теории чисел. Простые числа распределены неравномерно по всему диапазону чисел. Теорема формализует идею о том, что вероятность попадания простого числа между 1 и заданным числом становится меньше по мере роста числа. Эта вероятность равна n/ln(n), где ln(n) - функция натурального логарифма. Это означает, что вероятность встретить простое число с 2n цифрами примерно в два раза меньше, чем с n цифрами. Например, среди целых положительных чисел, содержащих не более 1000 цифр, примерно одно из 2300 является простым (ln 101000 ≈ 2302,6), тогда как среди целых положительных чисел, содержащих не более 2000 цифр, примерно одно из 4600 является простым (ln 102000 ≈ 4605,2). Другими словами, средний промежуток между последовательными простыми числами среди первых N целых чисел составляет примерно ln(N).
Пятнадцатилетний Карл Фридрих Гаусс в 1793 году заподозрил, что существует связь между простыми числами и логарифмами. Адриен-Мари Лежандр также заподозрил такую связь в 1798 году. Жак Хадамар и Шарль-Жан де Ла Валле Пуссен доказали теорему о простых числах в 1896 году, более чем через столетие после Гаусса.