Если обозначить через π(n) количество простых чисел, не превосходящих n, то теорема о распределении простых утверждает, что π(n) растёт как n/ln(n). Чем больше n, тем реже встречаются простые. Вблизи миллиона простой является примерно каждая 14-я величина. Вблизи миллиарда — примерно каждая 21-я.
π(n) считает простые числа до n и изображается синей ступенчатой функцией. Теорема о распределении простых утверждает: π(n) ~ n/ln(n), то есть их отношение стремится к 1 при n → ∞. Логарифмический интеграл Li(n) ещё точнее.
Гаусс предположил этот результат около 1800 года, изучая таблицы простых чисел. В 1896 году его независимо доказали Жак Адамар и Шарль-Жан де ла Валле-Пуссен, оба с помощью дзета-функции Римана и комплексного анализа. Полностью элементарное доказательство, без комплексного анализа, независимо нашли Сельберг и Эрдёш в 1948 году.
Таблица плотности простых чисел на разных масштабах.
| До n | Простых чисел π(n) | Плотность ≈ 1/ln(n) |
|---|---|---|
| 1 000 | 168 | 1 из 7 |
| 1 000 000 | 78 498 | 1 из 14 |
| 10⁹ | 50 847 534 | 1 из 21 |
| 10¹² | 37 607 912 018 | 1 из 28 |
Гипотеза Римана дала бы наилучшую возможную оценку ошибки: |π(n) - Li(n)| ≤ √n · ln(n) / (8π). Без неё мы знаем лишь, что ошибка имеет порядок o(n/ln(n)). Именно поэтому гипотеза Римана считается важнейшей открытой проблемой математики: она сказала бы нам, насколько точно можно предсказывать распределение простых чисел.
Более точным приближением для π(n), чем n/ln(n), является логарифмический интеграл Li(n) = интеграл от 2 до n от dt/ln(t). Гаусс предпочитал именно эту форму. Для n = 1 000 000 выражение n/ln(n) даёт 72 382, а Li(n) — 78 628 при точном значении 78 498. Ошибка Li(n) заметно меньше. Гипотеза Римана позволила бы оценивать её очень точно через √n · ln(n).