Теория чисел на Питергоре

Подсказка 1

Давайте попробуем посчитать количество чисел от n до n², которые делятся на простое p(тоже из этого отрезка). Как можно оценить это число?

Подсказка 2

Мы знаем, что таких чисел ровно [n²/p]. Но с целой частью работать не очень удобно, поэтому снизу можно поджать выражением n²/p - 1. А что можно сказать про разные p? Существуют ли числа из [n, n²], которые делятся на p₁ и p₂, если p₁ и p₂ из отрезка [n, n²]?

Подсказка 3

Все такие числа уникальны(то есть, для каждого p свой набор чисел, который делятся на p и пересечений по этим наборам нет). В таком случае, как можно оценить количество чисел из [n, n²], которые делятся на какое-то простое из [n, n²]?

Подсказка 4

Количество всех чисел — это Σ(n²/p - 1) по всем простым из нашего отрезка. А как её можно оценить сверху(помните, что мы смотрим на Количество чисел) и снизу?

Подсказка 5

Очевидно, что n² больше чем наша сумма, так как на рассматриваемом отрезке чисел: n² - n + 1. Оценку снизу получить сложнее, давайте посмотрим на Σ(n²/p), что из неё надо вычесть, чтобы получить сумму меньше, чем наша?

Подсказка 6

Если из Σ(n²/p) вычесть n², то мы получим сумму меньше чем наша, ведь количество слагаемых в сумме не больше n². Какие оценки мы получили и как из них получить оценку на Σ(1/p)?

Подсказка 7

Финальные оценки — это n² > Σ(n²/p - 1) > Σ(n²/p) - n². Остаётся сократить всё неравенство на n² и тогда получим, что сумма, которая нам нужна не превосходит 2.